试着理解滑动窗口

什么是滑动窗口

大多数人第一次接触滑动窗口（Sliding Window）算法应该是在学习 TCP 协议时。在 TCP 协议中，滑动窗口算法被用来进行流量控制，发送方和接收方均维护一个窗口，窗口大小根据流量变化而变化，从而使消息的发送方和接收方能够以一个合适的速度进行信息传输，从而达到流量控制的效果。而滑动窗口算法则是一个更加广泛的概念，其被广泛用于解决 连续性问题 ，如连续子数组，连续子串等。

能够使用滑动窗口解决的问题一般分为以下三类：

• 窗口大小固定
• 窗口大小不固定：寻找最大窗口
• 窗口大小不固定：寻找最小窗口

固定窗口

在固定滑动窗口问题中，我们初始化左右指针 l 和 r，分别表示窗口的左右边界，并确保窗口的大小始终固定不变。具体操作如下：

1. 初始化：将 l = 0；
2. 设置 r = l + windowSize - 1，使得窗口大小为 windowSize；
3. 同时移动 l 和 r，以固定步长向右滑动窗口；
4. 在每次滑动过程中，判断窗口内的元素是否满足题目要求的条件：
   • 如果满足：
     • 判断是否需要更新最优解（例如记录最小值、最大值、最大区间等），如有需要则更新；
   • 如果不满足：
     • 继续滑动窗口。

简言之，窗口大小不变，窗口整体向右滑动，每次判断当前窗口是否满足条件，并据此更新结果。

可变窗口

在可变滑动窗口问题中，我们同样初始化左右指针 l 和 r，分别表示窗口的左右边界。但处理逻辑略有不同，我们需要遵循以下步骤：

1. 初始化：将 l 和 r 均设为 0；
2. 扩展窗口：移动右指针 r（即 r++），将新元素加入窗口；
3. 判断当前窗口内的元素是否满足题目要求的条件：
   • 如果满足：
     • 视情况更新最优解（如记录当前窗口长度、起止位置等）；
     • 然后尝试移动左指针 l 来收缩窗口，直到不满足条件为止；
   • 如果不满足：
     • 继续移动右指针 r，扩大窗口。

简言之，右指针不断向右扩展窗口，左指针则在窗口满足条件时向右收缩，以探索更优解。

伪代码模板

text

初始化慢指针 = 0
初始化 ans

for 快指针 in 可迭代集合
   更新窗口内信息
   while 窗口内不符合题意
      扩展或者收缩窗口
      慢指针移动
   更新答案
返回 ans

例题

以 LeetCode 的 209. 长度最小的子数组 为例。

int minSubArrayLen(int s, vector<int>& nums) {
        int l = 0, total = 0;
        int ans = INT_MAX;

        for (int r = 0; r < nums.size(); ++r) {
		        // 更新窗口内信息
            total += nums[r];
            // 当窗口内信息满足要求时，尝试缩小窗口
            while (total >= s) {
		            // 更新答案
                ans = min(ans, r - l + 1);
                // 左指针右移 缩小窗口
                total -= nums[l];
                ++l;
            }
        }
				
				// 返回答案
        return ans == INT_MAX ? 0 : ans;
    }