【算法】滑动窗口 算法详解

1. 滑动窗口简介

滑动窗口（Sliding Window）是一种在计算机科学中用于解决各种子数组或子字符串问题的技术。滑动窗口技术通过维护一个固定大小的窗口在数组或字符串上移动，从而使得可以在较短的时间内解决一些复杂的问题。

滑动窗口使用一个左指针和一个右指针共同维护的一个区间，这个区间可以看作一个 “窗口”在 数组或字符串上滑动。窗口的长度可能是不变的，称为定长滑动窗口，也可能是变化的，称为不定长滑动窗口。这和双指针中的同向双指针很像，而滑动窗口本质上是同向双指针。

具体的滑动窗口的使用、滑动窗口的原理以及正确性将会在下面的题中展示。

2. OJ 练习

2.1 长度最小的子数组

题目链接——LCR 008. 长度最小的子数组 - 力扣（LeetCode）

思路一：暴力求解

这道题暴力求解就是枚举每一个区间然后求和，并更新最短的子区间。

for(int left = 0; left < n; left++){
	for(int right = left; right < n; right++){
        sum += nums[right];
        if(sum >= target)
            fmin(len, right - left + 1);
    }
    sum = 0;
}

可以看到十分的暴力，时间复杂度为 $O(n^2)$。

优化：由暴力求解到滑动窗口

我们来观察一下暴力求解的步骤：

首先在第一层循环的第一遍，当 right 已经到了一个满足条件的时候，如下：

到了这个时候还有必要往后再枚举吗？显然已经没有必要再枚举 right 后面的元素了，因为数组中的数都是正整数，所以 sum 在一次遍历中是单调递增的，而现在 sum 已经大于 target，再往后走和肯定更大，所以我们可以 直接跳过后面的遍历，直接来到循环的下一层。

这样做当然对，但是能不能再优化？我们有必要让 right 回退到和 left 重合然后又再继续遍历吗？我们不妨就只让 left++，然后 right 的位置不变，这样做是正确的吗？答案是肯定的。

我们来证明一下。left++ 之后的这个子数组区间无非就两种情况，一种是还满足 sum >= target，另一种就是 sum < target。

• 第一种情况，此时既然还满足情况，那不是正好，我找到了一个更小的子区间满足题意，此时我就只需要更新子区间的长度 len。

• 第二种情况，就是说现在不满足条件了，就是 sum 小了，那既然 right 不回退都小了，你还回退过去再遍历一遍干啥，回退遍历的那些子区间比现在这个更小，对吧。

综上所述，我们一共得到了两个优化：

• 当 right 已经到了满足条件位置的时候，直接跳过后面的遍历。
• left++ 的时候 right 不需要回退到 left 的位置。

优化之后，就变成了一个成型的滑动窗口，同时也是一种同向双指针。其中上图中的橙色部分就是两个指针所维护的一段区间，也叫做窗口。right++ 的过程叫做进窗口，left++ 的过程叫做出窗口。

滑动窗口的使用

1. 初始 left = 0，right = 0，充当窗口左端点，右端点。
2. 进窗口：++right。
3. 判断：根据判断决定是否出窗口（++left）。
4. 更新结果：2，3都有可能会更新结果，要看题目具体要求。

思路二：滑动窗口

int minSubArrayLen(int target, int* nums, int numsSize){
    int left = 0, right = 0;  // 窗口的左右端点
    int sum = 0, len = numsSize + 1;  // 由于最后要取最小的len，所以初始要往大了初始化
    while(right < numsSize){
        sum += nums[right];  // 把进窗口的数加到sum中
        while(sum >= target){  // 判断是否要出窗口
            len = fmin(len, right - left + 1);  // 更新len,选小的那个
            sum -= nums[left++];  // 出窗口时，sum先减去left对应的值，然后left再往后移
        }   
        ++right;  // 出循环说明不满足要求了，此时就进窗口
    }
    return len > numsSize ? 0 : len; 
}

2.2 最大连续 1 的个数

题目链接——1004. 最大连续1的个数 III - 力扣（LeetCode）

思路：滑动窗口 + zero计数器

这道题也是一个子区间问题，同样可以使用滑动窗口来解决。而这道题给了我们 k 次翻转 0 的机会，也就是说我们可以最多将 k 个 0 变成 1，然后再来计算最大连续 1 的个数。这个时候我们就可以用一个计数器来记录我们窗口中的 0 的个数，不断入窗口，如果窗口中的 0 的个数超了，那就出窗口。然后更新结果。

具体步骤：

1. 进窗口：是 0，计数器+1；是 1，不用管。
2. 判断：此时计数器有可能超了，所以要判断是否要出窗口。
3. 出窗口：如果出的是 0，计数器-1；是 1，不用管。
4. 更新结果：判断之后更新，因为判断之后 0 的个数才是符合题意的。

int longestOnes(int* nums, int numsSize, int k) {
    int left = 0, right = 0;  // 窗口的左右端点 
    int zero = 0;  // zero计数器
    int len = 0;  // 区间长度 
    while(right < numsSize){
        if(nums[right] == 0) ++zero;  // 如果进窗口的数是0，那么计数器就+1
        while(zero > k){  // 0的个数大于k就要考虑出窗口了
            if(nums[left] == 0){  // 出窗口的数是0，那么计数器-1
                --zero;
            }
            ++left;  // 继续出窗口直到0的个数小于k
        }
        len = fmax(len, right - left + 1);  // 出循环时0的个数是符合题意的，这时更新长度
        ++right;  // 进窗口
    }
    return len;
}

2.3 将 x 减到 0 的最小操作数

题目链接——1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

思路：逆向思维 + 滑动窗口

这道题直接做是比较困难的，看到 “最小操作数”，那直接选左右两边更大的去减 x 不就行了，当然不行，因为题目是说将 x “减到 0” 的最小操作数，有可能光选大了在某一次运算中就从正数直接减到负数了，到不了 0。所以你根本不知道这道题你到底要选左右两边哪个去减。因此正面直接做不好做，于是我们可以用 逆向思维 来解决。

既然你是两边的数去减 x 减到 0，假设我整个数组所有数的和是 numsSum，那么我就可以去找这个数组中间的某个连续子区间，让这个连续的子区间的和是 numsSum - x，且这个子区间的长度要最大。所以问题就转化成了 求和为 numsSum - x 的最大子区间长度。

接下来就可以用滑动窗口来解决这个问题。

int minOperations(int* nums, int numsSize, int x) {
    int left = 0, right = 0;  // 窗口的左右端点
    int sum = 0, numsSum = 0;  // 区间和，数组全部的和
    int len = -1;  // 子区间长度
    for(int i = 0; i < numsSize; i++){  // 求整个数组的元素和
        numsSum += nums[i];
    }
    int target = numsSum - x;  // 问题转化成和为target的最大子区间
    if(target < 0) return -1;  // 小于零说明整个区间和都没有x大，直接判-1
    while(right < numsSize){
        sum += nums[right];  // 把进窗口的数加到sum中
        while(sum > target){  // 判断是否需要出窗口
            sum -= nums[left++];  // 先减去最左边的数，然后再出窗口
        }
        if(sum == target) len = fmax(len, right - left + 1);  // 满足条件的时候才更新长度
        ++right;  // 入窗口
    }
    return len == -1 ? -1 : numsSize - len;

注意这里的子区间初始长度要定义成 -1 或者更小，不要定义为 0。这是有可能整个数组的所以元素和刚好等于 x，即 numsSum == x。这个时候滑动窗口记录的最大子区间的长度始终是 0，如果你初始化为 0 的话最后输出的时候用 return len == 0 ? -1 : numsSize - len 最后输出的就是 -1，而实际上应该输出 numsSize - len。