滑动窗口

场景引入

给你一个字符串 S 和一个字符串 T，在 S 中找到包含 T 所有字符的最短子串。暴力解法需要 O(n²) 枚举所有子串，能不能更快？

滑动窗口就是解决这类子串/子数组问题的利器。本质是维护一个可伸缩的窗口，在满足条件时收缩，不满足时扩张。

核心框架

滑动窗口的框架可以背下来，所有题目都是在这个框架上微调：

function slidingWindow(s) {
  const window = {}; // 窗口内的状态
  let left = 0, right = 0;

  while (right < s.length) {
    const c = s[right];
    right++; // 扩大窗口
    // ... 更新窗口内数据

    while (/* 窗口需要收缩的条件 */) {
      const d = s[left];
      left++; // 缩小窗口
      // ... 更新窗口内数据
    }
  }
}

关键点：

1. right 指针负责扩大窗口，逐个加入元素
2. left 指针负责收缩窗口，在满足条件时移除元素
3. 窗口的扩大和收缩时机因题而异，但框架不变

可视化演示

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

加载可视化中...

解题思路

以 LC 3 为例：

1. right 右移，把字符加入窗口
2. 如果窗口内出现重复字符（window[c] > 1），left 右移直到没有重复
3. 每次窗口合法时，更新最大长度

框架适配不同题目

题目	收缩条件	更新答案时机
最小覆盖子串	窗口包含了 T 的所有字符	收缩时更新最小长度
无重复最长子串	窗口内有重复字符	扩张后更新最大长度
字符串排列	窗口大小 ≥ T 的长度	收缩时检查是否匹配
字母异位词	窗口大小 ≥ T 的长度	收缩时检查是否匹配

复杂度分析

• 时间复杂度：O(n)。left 和 right 各最多遍历一次数组。
• 空间复杂度：O(k)，k 为字符集大小。

LeetCode 练习

按难度递进：

1. LC 3. 无重复字符的最长子串（中等）⭐
2. LC 567. 字符串的排列（中等）
3. LC 438. 找到字符串中所有字母异位词（中等）
4. LC 76. 最小覆盖子串（困难）⭐
5. LC 239. 滑动窗口最大值（困难，需要单调队列辅助）⭐