在算法设计中，滑动窗口是一种处理数组或字符串中子序列问题的极高效率手段。它通过将嵌套循环的 O(n^2) 复杂度降低到线性 O(n)。

---

1. 什么是滑动窗口？

滑动窗口可以看作是在数据结构（如数组或链表）上移动的一个“取景框”。

• 窗口（Window）：由左边界（left）和右边界（right）围成的区间。

• 滑动（Sliding）：窗口的边界根据特定条件向右移动。

核心思想

它利用了“已有的计算结果”。当窗口滑动时，我们不需要重新计算整个窗口内的值，而是通过“加入一个新元素，移出一个旧元素”的操作，在 O(1) 的时间内完成更新。

---

2. 滑动窗口的应用场景

滑动窗口通常用于解决以下三类问题：

类型	目标	示例
固定窗口	寻找长度固定的子数组特征	寻找数组中长度为 K 的最大平均值子数组
变长窗口（求最大）	寻找符合条件的最长子序列	寻找不包含重复字符的最长子串
变长窗口（求最小）	寻找符合条件的最小子序列	最小覆盖子串、和大于等于 K 的最小数组长度

---

3. 滑动窗口的操作流程

无论窗口大小是否固定，其核心逻辑都遵循四个步骤：

1. 入窗：右边界 right 向右移动，将新元素纳入窗口，更新内部状态。

2. 收缩：判断窗口是否满足（或不满足）特定条件，开始移动左边界 left。

3. 更新：在满足条件时，记录当前窗口的最优解（最大值、最小值、计数等）。

4. 循环：重复上述过程直至 right 到达数据末尾。

---

4. 通用代码模板（C/C++ 风格）

为了方便理解和复用，我们可以总结出一套通用的伪代码模板。

变长窗口模板（解决“最长/最小”子串类问题）

void slidingWindow(string s) {
    int left = 0, right = 0;
    int window_state = 0; // 记录窗口内的数据状态（如总和、频率等）

    while (right < s.size()) {
        // 【1. 入窗】：a 是将要移入窗口的字符
        char a = s[right];
        right++; 
        // 更新窗口内的数据逻辑
        UpdateState(a);

        // 【2. 收缩】：判断左侧窗口是否要收缩
        while (window_needs_shrink) {
            // 【3. 更新最优解】：如果是寻找最小区间，通常在这里更新结果
            updateResult(left, right);

            // d 是将要移出窗口的字符
            char d = s[left];
            left++;
            // 更新窗口内的数据逻辑
            RemoveState(d);
        }

        // 【4. 更新最优解】：如果是寻找最大区间，通常在这里更新结果
        updateResult(left, right);
    }
}

---

5. 为什么滑动窗口如此高效？

传统的暴力解法通过双重循环枚举所有子区间，复杂度为 O(n^2)。而滑动窗口的 left 和 right 指针都只增不减，即每个元素最多进窗一次、出窗一次。

因此，其总的时间复杂度为 O(2n)，即 O(n)。对于百万级数据处理，这种性能提升是质的飞跃。