zhangdizhangdi

3.无重复字符的最长子串

题目

LeetCode 中等

题目

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

示例：
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

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

题解

方法：Set + 双指针 + 滑动窗口

双指针 滑动窗口 Set

O(n) O(set 长度)

js
function lengthOfLongestSubstring(s) {
  const sLen = s.length
  if (sLen < 2) return sLen
  const tempSet = new Set()
  let maxLen = 0
  let l = 0
  for (let r = 0; r < sLen; r++) {
    const cur = s[r]
    console.log(r, cur)

    //从左指针的字符开始删，一直删到Set里没有当前字符
    while (tempSet.has(cur)) {
      const lStr = s[l]
      console.log('左指针：', l, lStr)
      tempSet.delete(lStr)
      ++l
    }

    tempSet.add(cur)
    maxLen = Math.max(maxLen, tempSet.size)

    console.log('左指针：', l, '，最长：', maxLen)
    console.log(tempSet)
  }
  return maxLen
}

console.log('🌰', lengthOfLongestSubstring('pwwkew'))
执行结果
0 p
左指针： 0 ，最长： 1
Set(1) { 'p' }
1 w
左指针： 0 ，最长： 2
Set(2) { 'p', 'w' }
2 w
左指针： 0 p
左指针： 1 w
左指针： 2 ，最长： 2
Set(1) { 'w' }
3 k
左指针： 2 ，最长： 2
Set(2) { 'w', 'k' }
4 e
左指针： 2 ，最长： 3
Set(3) { 'w', 'k', 'e' }
5 w
左指针： 2 w
左指针： 3 ，最长： 3
Set(3) { 'k', 'e', 'w' }
🌰 3

方法：Map + 双指针 + 滑动窗口

双指针 滑动窗口 Map

O(n) O(map 长度)

js
function lengthOfLongestSubstringUseMap(s) {
  const sLen = s.length
  const map = new Map()
  let maxLen = 0
  let l = 0
  for (let r = 0; r < sLen; r++) {
    const cur = s[r]
    console.log(r, cur)

    //map记录每个字符最新的位置，左指针可以直接指向后一位，不需要向上面Set那样循环删除
    if (map.has(cur) && map.get(cur) >= l) {
      l = map.get(cur) + 1
    }
    map.set(cur, r)

    maxLen = Math.max(maxLen, r - l + 1)

    console.log('左指针：', l, '，最长：', maxLen)
    console.log(map)
  }
  return maxLen
}

console.log('🌰', lengthOfLongestSubstringUseMap('abcabcbb'))
执行结果
0 a
左指针： 0 ，最长： 1
Map(1) { 'a' => 0 }
1 b
左指针： 0 ，最长： 2
Map(2) { 'a' => 0, 'b' => 1 }
2 c
左指针： 0 ，最长： 3
Map(3) { 'a' => 0, 'b' => 1, 'c' => 2 }
3 a
左指针： 1 ，最长： 3
Map(3) { 'a' => 3, 'b' => 1, 'c' => 2 }
4 b
左指针： 2 ，最长： 3
Map(3) { 'a' => 3, 'b' => 4, 'c' => 2 }
5 c
左指针： 3 ，最长： 3
Map(3) { 'a' => 3, 'b' => 4, 'c' => 5 }
6 b
左指针： 5 ，最长： 3
Map(3) { 'a' => 3, 'b' => 6, 'c' => 5 }
7 b
左指针： 7 ，最长： 3
Map(3) { 'a' => 3, 'b' => 7, 'c' => 5 }
🌰 3