算法滑动窗口
,

无重复字符的最长子串

文章目录
  1. 1. 题目描述
  2. 2. 分析
    1. 2.1. 滑动窗口

无重复字符的最长子串

题目描述

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

分析

  1. 使用什么方法呢？
    1. 每个是不是都是 ascii 码？如果是就尝试使用ascii做映射做
    2. 滑动窗口，从左向右滑动
    3. 动态规划缩小范围

先使用滑动窗口的方法做

滑动窗口

  1. 要有左右指针指明窗口位置，大小
  2. 右指针先行走做遍历，左指针根据具体条件向右滑动
  3. 当右指针走到尽头，遍历结束

题目分析：

1
2
3
4
5
6
7
left, right = 0
right: 0 -> n
  left 向右移动条件：
   s[right]是否存在在窗口子串中
   left 移动到窗口子串中字符 s[right] 的下一个位置
   记录长度length
返回 max(right - left, length)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func lengthOfLongestSubstring(_ s: String) -> Int {
  var len = 0
  var left = s.startIndex
  var right = left

  var window = ""

  while right != s.endIndex {
    let curChar = s[right]
    if window.contains(curChar) {
      let index = window.firstIndex(of: curChar)!
      let distance = window.distance(from: window.startIndex, to: index)
      left = s.index(left, offsetBy: distance + 1)
    }
    right = s.index(after: right)
    window = String(s[left..<right])
    len = max(len, s.distance(from: left, to: right))
  }

  return len
}

leetcode 结果
104 ms	21.1 MB	Swift

使用 hashMap 缓存window 以后优化执行时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func lengthOfLongestSubstring(_ s: String) -> Int {
  var itemMap: [Character: Int] = [:]
  var left = 0, right = 0
  var len = 0
  
  for e in s {
    if let idx = itemMap[e] {
      //1. 使用max 去掉 left 之前的元素，之前是这样会有问题left = idx + 1
      left = max(idx + 1, left)
    }
    itemMap[e] = right
    len = max(len, right - left + 1)
    right += 1
  }
  
  return len
}

44 ms	21.1 MB

对于上面注释的 1，如果使用 left = idx + 1 的话 eg “abba”
当 curr 指针指到第二个 b 时，left = 2
当 curr 指针指到第二个 a 时，left = 1
我们要做的是如何把 itemMap 中第二个 b 之前不在 window 的元素清空掉？
因为结果是 index 相关，所以直接使用 max 就可以了 left = max(idx + 1, left)

P.S: 使用 max方法截断数组