前端知库

滑动窗口怎样求无重复字符的最长子串？

用左右两个指针围出一个窗口，右指针不断向右扩，遇到窗口里已有的字符，就把左指针移到这个字符上次出现位置的后一位。用 Map 记录每个字符最后出现的下标，每个字符最多进出窗口一次，整体 O(n)。

参考答案

简答

题目是：给一个字符串，找出不含重复字符的最长子串的长度，比如 abcabcbb 的答案是 3，对应 abc。暴力做法是枚举所有子串再逐个检查，至少 O(n²)。

滑动窗口的思路是：用 left 和 right 两个下标围出一段子串，保证这段里始终没有重复字符。right 每次往右走一格，把新字符纳入窗口；如果这个字符在窗口里已经出现过，就把 left 跳到它上次出现位置的后一位，把重复的那个踢出去。每一步都更新一次最长长度。

怎么快速知道字符上次出现在哪？用 Map 记录“字符 → 最后出现的下标”。因为 left 和 right 都只往右走、不回头，每个字符最多被处理两次，整体 O(n)。

要注意，Map 里记录的位置可能已经在窗口左边了。比如 abba 走到最后的 a 时，a 上次出现在下标 0，可窗口左边界早就是 2 了，这时 left 不能往回跳，所以要取 Math.max(left, 上次位置 + 1)。

代码实现

JavaScript
function lengthOfLongestSubstring(s) {
  const lastIndex = new Map();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    if (lastIndex.has(char)) {
      left = Math.max(left, lastIndex.get(char) + 1);
    }
    lastIndex.set(char, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

console.log(lengthOfLongestSubstring('abcabcbb')); // 3
console.log(lengthOfLongestSubstring('bbbbb')); // 1
console.log(lengthOfLongestSubstring('pwwkew')); // 3
console.log(lengthOfLongestSubstring('abba')); // 2
console.log(lengthOfLongestSubstring('')); // 0

pwwkew 为什么是 3？走到第二个 w（下标 2）时，窗口 pw 里已经有 w，在下标 1，于是 left 跳到 2，窗口变成 w。之后加入 k、e，窗口是 wke，长度 3。再遇到 w 时，上次的 w 在下标 2，left 跳到 3，窗口变成 kew，长度还是 3。

abba 就是简答里说的情况。走到第二个 b 时 left 跳到 2；再走到最后的 a，Map 里 a 在下标 0，0 + 1 = 1 比当前的 left 小，如果不取较大值，left 就退回到 1，窗口变成 bba，里面有重复，结果错成 3。

这里按 s[right] 逐个取的是 UTF-16 编码单元，emoji 这类字符会被拆成两半。要按用户看到的字符处理，可以先用 Array.from(s) 拆分，见《为什么字符串 length 不一定等于用户看到的字符数？》。

滑动窗口适合哪些题

题目要找“满足某个条件的最长或最短连续子串、子数组”，而且窗口扩大、缩小时条件能增量更新，就适合滑动窗口。比如和大于等于目标值的最短子数组、包含所有指定字符的最小覆盖子串、长度为 k 的子数组最大平均值。

套路是固定的：右指针扩张，把新元素加入窗口状态；窗口不满足条件时，左指针收缩，把元素移出状态；在合适的时机更新答案。

常见追问

滑动窗口和双指针是什么关系？

滑动窗口是双指针的一种，两个指针同向移动，中间夹着一个窗口。另一种常见的双指针是两头往中间走，比如有序数组找两数之和、判断回文串。

前端开发里用得到吗？

思路很常见。比如统计最近一分钟内的请求次数做限流，就是在时间轴上维护一个窗口，新请求进来，过期的请求移出去。

MDN · Map
反馈此题