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

题目

LeetCode 中等

题目

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

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

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

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

题解

时间复杂度：O(N)

这里的 N是字符串的长度。
右指针 right 从头走到尾，恰好遍历一次数组。左指针 left 直接通过 Map/Set 获取目标位置进行跳跃，不需要像普通的滑动窗口那样一步一步 while 循环去慢慢收缩。所以每个字符最多被访问一次，时间复杂度是非常优秀的 O(N)。
空间复杂度：O(Σ) 或 O(1)

这里的 Σ 是字符集的大小。
因为我们使用了一个 Map/Set。如果字符串只包含英文字母、数字、符号和空格（ASCII 码），那么 Map 最多只会存储 128 个键值对。由于 128 是一个常数，所以空间复杂度可以认为是 O(1)。
如果字符集非常大（比如全 Unicode 字符集），空间复杂度为 O(Σ)，最坏情况下也是 O(N)（所有字符都不重复）。

方法：Set + 滑动窗口

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
{}
♻️ 1 w
左指针： 0 ，最长： 2
{}
♻️ 2 w
左指针： 0 p
左指针： 1 w
左指针： 2 ，最长： 2
{}
♻️ 3 k
左指针： 2 ，最长： 2
{}
♻️ 4 e
左指针： 2 ，最长： 3
{}
♻️ 5 w
左指针： 2 w
左指针： 3 ，最长： 3
{}
🌰 3

方法：Map + 滑动窗口

function lengthOfLongestSubstring(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('🌰', lengthOfLongestSubstring('abcabcbb'))

执行结果

♻️ 0 a
左指针： 0 ，最长： 1
{}
♻️ 1 b
左指针： 0 ，最长： 2
{}
♻️ 2 c
左指针： 0 ，最长： 3
{}
♻️ 3 a
左指针： 1 ，最长： 3
{}
♻️ 4 b
左指针： 2 ，最长： 3
{}
♻️ 5 c
左指针： 3 ，最长： 3
{}
♻️ 6 b
左指针： 5 ，最长： 3
{}
♻️ 7 b
左指针： 7 ，最长： 3
{}
🌰 3

本页目录