算法模板 - 滑动窗口模板

1. 核心思路

「滑动窗口」是常见且高效的算法技巧，用来在一个序列（如数组、字符串）中寻找满足某些条件的 连续子区间。它使用两个指针（通常称为 left 和 right）来标记窗口的左右边界，随着 right 不断向右移动来扩大窗口，并在合适的时候移动 left 来缩小窗口，从而在一次（或两次）线性扫描中得到所需的解。

应用滑动窗口的典型问题包括：

1. 最小覆盖子串：在字符串 s 中找到包含 t 所有字符的最小子串；
2. 最长无重复子串：在字符串 s 中找出不含重复字符的最长子串；
3. 满足某些频率或次数限制：如找出含有某些字符次数不超过 K 的最长/最短子串；
4. 大小固定或可变的子数组：在数组中找大小为 K 的连续子数组的特征（和、平均值、最大最小值等）。

2. 时间复杂度

与传统的「双重循环」方案相比，滑动窗口能大大减小时间开销。因为：

• 右指针 right：从左到右只走一遍；
• 左指针 left：同样只会从左往右移动一次（在必要时收缩窗口）。

因此，两个指针各自最多只移动 n（字符串或数组长度）次，总的时间复杂度为 O(n)。这是滑动窗口算法非常重要的优势。

3. 滑动窗口的适用场景

1. 连续区间/子串/子数组：如果题目要求「在连续子区间/子串中满足某条件」，往往可以尝试滑动窗口。
2. 线性扫描可行：如果一个问题可以通过左右指针（或上下边界）在线性序列中移动来穷尽所有“候选窗口”，就具备使用滑动窗口的潜力。
3. 子区间的条件可通过增/减元素迅速更新：一般来说，滑动窗口依赖于在进入/移出窗口时能快速地更新状态（如字符计数、元素总和等）。

4. 滑动窗口模板

下面这个模板以「字符串」为载体，并用 HashMap<Character, Integer> 来统计窗口内每个字符的出现次数。对于数组，也可以将 window 改成 HashMap<Integer, Integer> 或其他适合的结构。

/* 滑动窗口算法通用框架 */
void slidingWindow(String s) {
    // window记录窗口中各字符的出现次数，可以根据具体问题修改数据结构
    HashMap<Character, Integer> window = new HashMap<>();

    int left = 0; // 初始化左指针
    int right = 0; // 初始化右指针
    
    while (right < s.length()) {
        // c是将要移入窗口的字符
        char c = s.charAt(right);
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        // 这里填写增大窗口时的逻辑，例如：
        window.put(c, window.getOrDefault(c, 0) + 1);
        // ...

        // 判断左侧窗口是否要收缩
        while (left < right && /* 这里填写窗口收缩的条件 */) {
            // d是将要移出窗口的字符
            char d = s.charAt(left);
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            // 这里填写缩小窗口时的逻辑，例如：
            window.put(d, window.getOrDefault(d, 0) - 1);
            // ...
        }
    }
    // 根据具体问题返回所需的答案或结果
}

4.1 两处「...」详解

在上文模板中，我们在「扩大窗口」和「缩小窗口」时都留了 ... 代表需要根据具体题目来填充逻辑，这里简单举例：

1. 扩大窗口时的逻辑
   • 更新 window 中字符计数（如 window.put(c, window.getOrDefault(c, 0) + 1)）。
   • 更新满足条件的计数器，如「多少字符的出现次数达到了所需」或「窗口中不同字符的个数」等。
2. 缩小窗口时的逻辑
   • 更新 window 中被移除字符的计数（window.put(d, window.get(d) - 1)）。
   • 若某字符计数变为 0，可以将其从 window 移除，保证数据干净。
   • 更新计数器，如果某个字符的数量变化影响到了题目要求，应在此处理。

4.2 具体应用示例

1. 最小覆盖子串
   • 需要在窗口中记录目标字符串 t 的字符频率，并比较当前窗口的字符频率是否满足「覆盖所有 t 字符」。
   • 每次扩大窗口，尝试加入新字符；若已满足覆盖条件，则缩小窗口看是否还能满足覆盖，同时更新最优解（最小长度）。
2. 最长无重复子串
   • 窗口需要保证「无重复字符」，当右指针加入一个新字符，如果该字符已在窗口中出现，说明有重复，则需要移动左指针收缩窗口，直到没有重复为止。
   • 不断更新「最大窗口长度」作为结果。
3. 固定大小子数组统计
   • 当 right - left + 1 超过固定大小 K 时，就需要收缩窗口 left++ 以保持窗口大小不超过 K，窗口内部可能需要维护子数组的和、平均值或其他统计信息。
4. 其他常见场景
   • 在数组/字符串中找「大于/小于某个值」的最短子数组；
   • 字符型题目中找「含某些特殊字符数不超过 X 的最长子串」等。

5. 算法总结

滑动窗口是一种双指针策略，在一次或两次线性扫描内完成对所有可能子区间（窗口）的遍历：

• 优势：
  1. 效率高：线性时间复杂度 O(n)。
  2. 灵活可扩展：可以配合哈希表、计数器等，根据题目需求调整。
• 注意点：
  1. 在「扩大窗口」和「缩小窗口」时，逻辑通常是镜像且对称的。
  2. 需要精确定义「窗口」的含义，以及「何时需要收缩」的条件。
  3. 别忘了在移动指针前后更新或记录结果，特别是当题目需要最优解时，每一次窗口变化可能都要检查是否更新答案。
• 与其他算法相比：
  1. 与暴力枚举所有子串（时间复杂度 O(n^2)）相比，滑动窗口大大提升了效率。
  2. 与分治法或回溯法相比，滑动窗口更适用于连续区间的问题，并能在 O(n) 时间内解决。

总而言之，滑动窗口框架是处理「连续子数组/子串」问题的重要利器。只要在「扩大窗口」和「缩小窗口」阶段巧妙地维护数据结构，就能满足绝大部分需要在线性时间解决的此类问题。