文档目录

一、什么是滑动窗口？

核心思想：在数组/字符串上维护一个"窗口"，通过移动窗口的左右边界，在一次遍历中解决问题。

滑动窗口解决的核心问题是"子数组/子串"类问题——传统需要 $O(N^2)$ 嵌套循环，滑动窗口降到 $O(N)$。

两种窗口：

  • 定长窗口：窗口大小固定，像火车一样整体平移。
  • 不定长窗口：窗口大小动态变化，右边界不断扩张，左边界按条件收缩。

二、不定长窗口——无重复字符的最长子串（LeetCode 3）

问题：给定字符串，找出不包含重复字符的最长子串长度。

思路：

s = "abcabcbb"

窗口演变（用 set 或 map 记录窗口内字符）：
[a]           left=0, right=0 → 不重复，窗口扩大
[a b]         left=0, right=1 → 不重复，窗口扩大
[a b c]       left=0, right=2 → 不重复，窗口扩大
[a b c a]     left=0, right=3 → 'a' 重复！左边界右移
  [b c a]     left=1, right=3 → 不重复，窗口扩大
  [b c a b]   left=1, right=4 → 'b' 重复！左边界右移
    [c a b]   left=2, right=4 → 不重复
    ...继续

最大窗口长度 = 3（"abc" 或 "bca" 或 "cab"）

整体操作流程：

  1. 初始化：创建一个数组 last_seen 记录每个字符上次出现的索引（初始为 -1），左指针 left = 0。
  2. 扩展右边界：遍历字符串，每次将右指针 right 指向的字符纳入窗口。
  3. 检测重复并收缩：如果当前字符在窗口内出现过（last_seen[c] >= left），将左边界跳到重复字符的下一个位置（left = last_seen[c] + 1）。
  4. 更新位置：更新当前字符的最新出现位置为 right。
  5. 更新结果：计算当前窗口长度 right - left + 1，更新全局最大值。
  6. 返回结果：遍历结束后返回最大长度。
int lengthOfLongestSubstring(string s) {
    vector<int> last_seen(128, -1);              // ① 记录每个字符上次出现的索引
    int max_len = 0;
    int left = 0;                                // ② 左指针（窗口左边界）

    for (int right = 0; right < s.size(); right++) {// ③ 右指针向右扩展
        char c = s[right];

        if (last_seen[c] >= left) {              // ④ c 在窗口内重复了
            left = last_seen[c] + 1;             // ⑤ 左边界跳到重复字符之后
        }

        last_seen[c] = right;                    // ⑥ 更新 c 的最新位置
        max_len = max(max_len, right - left + 1);// ⑦ 更新最大窗口长度
    }

    return max_len;
}

关键点：用 vector<int>(128, -1) 比 unordered_map 更快（哈希表有计算开销），因为 ASCII 字符范围有限，用数组直接索引。

时间复杂度：$O(N)$。right 遍历一次，left 只右移不左移。 空间复杂度：$O(1)$。固定 128 大小的数组。

三、不定长窗口——最小覆盖子串（LeetCode 76）

问题：在 s 中找到包含 t 所有字符的最短子串。

这是滑动窗口最难的模板题，掌握了这道题，所有"找包含某集合的最短子串"都能做。

思路：

s = "ADOBECODEBANC", t = "ABC"

1. 先统计 t 中每个字符需要几个：{A:1, B:1, C:1}
2. 右边界不断扩张，直到窗口覆盖了 t 的所有字符
3. 然后收缩左边界，找到最短的覆盖子串
4. 重复：右边界再扩张，寻找下一个覆盖窗口

窗口过程：
[A]           还需 B,C
[A D]         还需 B,C
[A D O]       还需 B,C
[A D O B]     还需 C ← 有 A 和 B 了
[A D O B E]   还需 C
[A D O B E C] 全了！窗口 "ADOBEC"，尝试收缩
  [D O B E C] 还有 (但只有 D 被移除)
  [O B E C]   不够了 (A 没了) → 右边界继续

[O B E C O]   还需 A
[O B E C O D] 还需 A
[O B E C O D E] 还需 A
[O B E C O D E B] 还需 A
[O B E C O D E B A] 全了！"ODEBANC"
  [B E C O D E B A] 收缩 → "BECODEBA"
  [E C O D E B A]   → "ECODEB A"
  [C O D E B A]     → "CODEBA"
  [O D E B A]       不够了 → 右边界继续...

最终最短的覆盖子串 = "BANC"

整体操作流程：

  1. 初始化需求：统计 t 中每个字符的出现次数到 need 数组，required = t.size() 记录还需要匹配的字符总数。
  2. 扩展右边界：遍历 s，每次将 s[right] 纳入窗口，need[rc]--。如果该字符是 t 中需要的（need[rc] > 0），required--。
  3. 检查是否覆盖：当 required == 0 时，说明当前窗口已包含 t 的所有字符。
  4. 收缩左边界：在 required == 0 的情况下，尝试收缩左边界：
    • 记录当前窗口长度，更新最短结果。
    • 将 s[left] 移出窗口，need[lc]++。
    • 如果 need[lc] > 0，说明移出的字符是 t 需要的且不够了，required++。
  5. 重复：回到步骤 2 继续扩展右边界，寻找下一个覆盖窗口。
  6. 返回：返回最短覆盖子串（若未找到则返回空串）。
string minWindow(string s, string t) {
    if (s.size() < t.size()) return "";

    vector<int> need(128, 0);                    // ① need[c] > 0 表示还缺 c
    for (char c : t) need[c]++;                  // ② 统计 t 中每个字符的需求量

    int left = 0, right = 0;
    int min_len = INT_MAX, min_start = 0;
    int required = t.size();                     // ③ 还需匹配的字符总数

    while (right < s.size()) {                   // ④ 右边界遍历整个 s
        char rc = s[right];
        right++;

        if (need[rc] > 0) required--;            // ⑤ rc 是需要的 → 匹配数减一
        need[rc]--;                              // ⑥ rc 纳入窗口（need 可为负，表示多余）

        while (required == 0) {                  // ⑦ 窗口已覆盖 t 的所有字符
            int len = right - left;
            if (len < min_len) {                 // ⑧ 更新最短覆盖子串
                min_len = len;
                min_start = left;
            }

            char lc = s[left];
            left++;                              // ⑨ 收缩左边界

            need[lc]++;                          // ⑩ lc 移出窗口，需求恢复
            if (need[lc] > 0) required++;        // ⑪ 移出后不够了 → required++
        }
    }

    return min_len == INT_MAX ? "" : s.substr(min_start, min_len);
}

时间复杂度：$O(N)$。right 遍历一次 + left 最多移动 N 次。 空间复杂度：$O(1)$。固定 128 数组。

四、定长窗口——字符串排列（LeetCode 567）

问题：s2 是否包含 s1 的排列（即 s1 的某个排列是 s2 的连续子串）。

思路：

s1 = "ab", s2 = "eidbaooo"

固定窗口大小为 s1.size() = 2
窗口在 s2 上滑动：

[e i] → a:0,b:0? → 不匹配（需要 a=1,b=1）
[i d] → a:0,b:0? → 不匹配
[d b] → a:0,b:1? → a 不够
[b a] → a:1,b:1 ✅ 匹配！

整体操作流程：

  1. 长度检查：如果 s1 比 s2 长，直接返回 false。
  2. 初始化需求：统计 s1 中每个字符的出现次数到 need 数组，required = s1.size() 记录还需匹配的字符数。
  3. 滑动窗口遍历 s2：
    • 扩展右边界，纳入 s2[right]，更新 need 和 required。
    • 定长控制：如果窗口大小超过了 s1.size()，收缩左边界（移出左侧字符，恢复 need 和 required）。
    • 匹配检测：如果 required == 0 且窗口大小等于 s1.size()，说明找到了一个排列，返回 true。
  4. 遍历结束：未找到匹配，返回 false。
bool checkInclusion(string s1, string s2) {
    if (s1.size() > s2.size()) return false;     // ① s1 比 s2 长 → 不可能

    vector<int> need(26, 0);                     // ② 26 个小写字母
    for (char c : s1) need[c - 'a']++;           // ③ 统计 s1 中字符需求

    int left = 0, right = 0;
    int required = s1.size();                    // ④ 还需匹配的字符数

    while (right < s2.size()) {                  // ⑤ 右边界遍历 s2
        char rc = s2[right];
        right++;

        if (need[rc - 'a'] > 0) required--;      // ⑥ rc 是需要的 → 匹配数减一
        need[rc - 'a']--;

        if (right - left > s1.size()) {           // ⑦ 窗口超过定长 → 收缩左边界
            char lc = s2[left];
            left++;
            need[lc - 'a']++;
            if (need[lc - 'a'] > 0) required++;
        }

        if (required == 0 && right - left == s1.size()) {
            return true;                         // ⑧ 找到匹配的排列
        }
    }

    return false;                                // ⑨ 未找到
}

时间复杂度：$O(N)$。固定窗口一次遍历。

五、滑动窗口通用模板（面试直接套）

int slidingWindow(string s) {
    // ① 用数组/哈希表记录窗口内的状态
    vector<int> window(128, 0); // 或 unordered_map

    int left = 0, right = 0;
    int result = 0;  // 根据问题定义

    while (right < s.size()) {
        // ② 移入右边界字符，更新窗口
        char rc = s[right];
        right++;
        // 更新窗口状态...

        // ③ 收缩左边界（条件取决于问题）
        while (/* 窗口需要收缩的条件 */) {
            char lc = s[left];
            left++;
            // 更新窗口状态...
        }

        // ④ 更新结果（此时窗口满足条件）
        result = max(result, right - left);
    }

    return result;
}

六、面试追问 Q&A

Q1：滑动窗口什么时候不能用？ A：当问题的解不连续时不能用。滑动窗口要求解是一段连续的区间。如果问题允许跳过元素（如"最长子序列"而非"最长子串"），滑动窗口不适用，要用 DP。

Q2：定长窗口和不定长窗口怎么选？ A：题目明确说"大小为 k 的子数组/子串"就是定长。题目说"某个条件成立的最大/最小窗口"就是不定长。最小覆盖子串是不定长收缩到最短；无重复字符是最长所以不定长扩大。

Q3：vector<int>(128) 和 unordered_map<char,int> 选哪个？ A：字符串题目（字符范围有限）用 vector<int>(128)，这是数组索引，比哈希表快 5-10 倍。如果键是更一般的类型，才用 unordered_map。

Q4：三数之和的 while (left < right) 里为什么有去重？ A：如果不跳过重复元素，比如 [-1, -1, 0, 1, 2]，固定 -1 时 left 在第二个 -1 上，会得到重复的 [-1, 0, 1]。去重保证三元组唯一，但 left++ 和 right-- 后的去重不能漏掉合法解（先记录结果，再跳重复）。