滑动窗口方法论 ​

滑动窗口是处理连续子数组/子串问题的利器。它本质上是双指针的一种特殊应用——用两个指针维护一个"窗口"，通过窗口的滑动来高效遍历所有可能的子区间。

什么是滑动窗口？ ​

想象你正在用一个可伸缩的相框在一幅长画卷上移动。相框框住的部分就是"窗口"，你可以：

• 向右扩展窗口（右边界右移）
• 从左收缩窗口（左边界右移）

数组: [a, b, c, d, e, f, g, h]
           ├─────────┤
          left     right
          └── 窗口 ──┘

为什么需要滑动窗口？ ​

以"找最长无重复子串"为例：

暴力解法：枚举所有子串，检查是否有重复。

• 子串数量：O(n²)
• 每次检查：O(n)
• 总时间：O(n³)

滑动窗口：维护一个无重复的窗口，不断扩展和收缩。

• 每个元素最多进窗口一次，出窗口一次
• 总时间：O(n)

滑动窗口的核心思想 ​

滑动窗口之所以高效，关键在于增量更新：

• 窗口扩展时，只需要处理新加入的元素
• 窗口收缩时，只需要处理移出的元素

不需要每次都重新计算整个窗口的状态。

滑动窗口的两种类型 ​

1. 固定窗口 ​

窗口大小固定为 k，每次整体向右滑动一格。

大小为 3 的窗口：
[a, b, c] d, e, f → 窗口 1
a, [b, c, d] e, f → 窗口 2
a, b, [c, d, e] f → 窗口 3

适用场景：

• 求大小为 k 的子数组的最大和
• 求大小为 k 的子数组的平均值

2. 可变窗口 ​

窗口大小不固定，根据某个条件动态调整。

找满足条件的最长子串：
- 条件满足 → 扩展右边界，尝试更长
- 条件不满足 → 收缩左边界，直到满足

适用场景：

• 最长无重复子串
• 最小覆盖子串
• 满足条件的最长/最短子数组

滑动窗口的通用框架 ​

function slidingWindow(arr: any[]) {
  let left = 0;
  const window = new Map();  // 或其他数据结构维护窗口状态
  
  for (let right = 0; right < arr.length; right++) {
    // 1. 右边界扩展，元素入窗
    const entering = arr[right];
    // 更新窗口状态...
    
    // 2. 判断是否需要收缩左边界
    while (需要收缩的条件) {
      const leaving = arr[left];
      // 更新窗口状态...
      left++;
    }
    
    // 3. 更新结果（根据题目要求）
  }
}

滑动窗口适用的问题特征 ​

• 问题涉及连续的子数组或子串
• 需要求满足某条件的最长或最短子区间
• 可以用某种数据结构高效维护窗口状态
• 窗口的扩展和收缩具有单调性

常见的窗口状态维护方式 ​

本章目标 ​

掌握滑动窗口后，你将能够高效解决：

• 最长/最短子串问题
• 子数组和问题
• 字符串匹配问题（排列、异位词）
• 含有限制条件的子区间问题

接下来，我们将深入学习固定窗口和可变窗口的具体技巧。