LeetCode 无重复字符的最长子串 JavaScript 滑动窗口题解

题目

无重复字符的最长子串

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

先明确一点：子串要求连续，跟子序列不同。所以候选的答案总是原字符串中的一段连续区间，这就是能用滑动窗口的前提。

暴力解法是枚举所有起点和终点，再逐个检查区间内有没有重复，那是 O(n^3)，加上哈希优化检查也还是 O(n^2)。

解题思路

用双指针维护一个滑动窗口，用来剪切子串
不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位
过程中，记录所有窗口的长度，并返回最大值

滑动窗口能把复杂度降到 O(n)，靠的是一个关键性质：左指针永远不需要往回走。

想清楚为什么。假设当前窗口 [l, right] 内部无重复，右指针前进一位遇到了重复字符，那么重复的那个字符必然就在窗口里的某个位置 k。此时任何以 l 到 k 之间为起点的窗口，都必然包含这两个重复字符，不可能是合法答案，可以整批跳过——所以左指针直接跳到 k + 1，中间那些位置一个都不用试。

正因为两个指针都只单向前进，各自最多走 n 步，总时间才是 O(n)。这也是滑动窗口和暴力枚举的本质差别：不是优化了检查的速度，而是证明了大量候选区间根本不需要检查。

第二步里「左指针移动到重复字符的下一位」需要知道重复字符在哪，所以要有个东西记住每个字符最近一次出现的下标，这就是代码里 map 的作用。

题解

var lengthOfLongestSubstring = function (s) {
  // 左指针的位置
  let l = 0;
  // 这个结果在循环中每次都会记录一下
  let res = 0;
  const map = new Map();
  // 循环中的 right 理解为右指针，每次都会加 1
  for (let right = 0; right < s.length; right++) {
    const val = s[right];

    // 当遇到重复字符时，找出重复字符在 map 对应的位置然后加一，这样左指针就移动到了重复字符的下一位
    // map.get(val) >= l 表示重复字符必须是滑动窗口里的重复字符
    if (map.has(val) && map.get(val) >= l) {
      l = map.get(val) + 1;
    }
    // 计算每一次左指针与右指针之间的间隔数量，取与 res 之中的最大值
    res = Math.max(res, right - l + 1);

    map.set(val, right);
  }
  return res;
};

整段代码里最容易写错、也最值得琢磨的是那个 map.get(val) >= l 的判断。

map 记录的是每个字符最后一次出现的下标，但它只增不删——字符被左指针甩出窗口后，记录还留在 map 里。所以 map.has(val) 为真只能说明这个字符在整个字符串里出现过，不能说明它在当前窗口内。必须再确认它的下标不小于 l，才算是窗口内的重复。

漏掉这个条件会导致左指针往回跳。举个例子，字符串 abba：走到第二个 b 时 l 变成 2；再走到最后那个 a，map 里 a 的记录是 0，如果不判断就把 l 设成 1，左指针从 2 退回到 1，窗口反而变大了，结果算成 3，而正确答案是 2。这是这道题最经典的错误。

另一处细节是 right - l + 1，加一是因为两端都算在内。窗口 [2, 3] 的长度是 2 不是 1。

还有 map.set(val, right) 放在最后执行。此时的下标一定是这个字符最新的位置，覆盖旧记录正是我们要的行为，因为判断重复时只关心「最近一次出现在哪」。

时间复杂度：O(n)
空间复杂度：O(m) m 是字符串中不重复字符的个数，存储在 map 中，

空间上 m 有个天然上界——字符集大小。如果输入限定为小写字母，m 最多 26，也就是 O(1)；ASCII 则不超过 128。所以这类题也常用一个定长数组代替 Map，用字符编码当下标，省掉哈希计算的开销，跑得更快。

下图是滑动窗口移动过程的示意，可以对照着看左右指针各自什么时候前进。