2024年11月3日练习（滑动窗口算法）

一.LCR 008. 长度最小的子数组 - 力扣（LeetCode）

1.题目描述：

首先这个数组里面全是正整数，就是在这个数组中找出一个连续的区间的和要大于等于目标值，然

后要找长度最小的区间才行，如果不存在就返回0.

这里我们来看一个例子：

这里我们可以明显看出深蓝色画的横线满足大于等于目标值且区间长度最小是2，所以这个例子返

回的长度就是2.

2.算法描述：

    方法一：暴力解法

            那么就是暴力枚举出所有子数组的和，然后判断哪个是满足题目条件的，那么暴力枚举的

时间复杂度是多少呢？此时肯定是两个指针来解决，那么此时就是O(n^2),但是此时两个指针不在

同一位置，再次遍历一下去求和，那么其实真正的时间复杂度就是O(n^3).

   方法二：

            那么这里我们来优化一下暴力解法，既然题目已经说了，这个数组的所有元素都是正整

数，那么当我们数越多，那么所得到的和就会越大。既然这样我们就可以利用一下单调性来优化一

下。

我们先简单优化一下暴力枚举解法：

就是在定义left和right指针的时候再定义一个sum，每走一步就加到sum上去：

这样就省去了，再从开头遍历去求和的步骤，这样时间复杂度就变成了O(n^2)了

现在我们就来模拟一下：

此时我们找到一个大于7的子数组，接下来当我们right继续右移的时候，那肯定是必定大于7的，

因为整个数组是正整数构成的，就算继续往后找，虽然符合大于7这个要求，但是你的数组长度也

在增加，肯定就不会是最终结果了，所以就无需往后移动了。

那么既然找到一组，我们接下来就要去换一组了，那么在暴力解法中我们先让left++，再让right调

整到left的位置，再走一遍，但是此时这样很麻烦，既然我们要找长度最小的，我们仅需让

left++，然后求left到right这个子数组的和时，直接让上个sum减去之前left指向的数即可求出这个

和：

这样我们就发现了这样的两个规律，此时我们就利用单调性，使用“同向双指针”“来优化这个暴力解

法，这里同向双指针也叫做滑动窗口。因为上面说了right是不会回退的，一直往前走的。

这两个指针就像是一个窗口一样在这个数组里面滑来滑去，所以我们叫做滑动窗口的算法。

当我们利用单调性，而且我们做题目两个指针不回退，都向同一个方向前进的时候，此时我们就利

用滑动窗口的算法来解决问题。

滑动窗口的用法，其实上面的图示操作也就是滑动窗口的用法：

这个right就相当于窗口的边边，此时已经算是进窗口了，所以sum=2，现在判断此时的值是小于7

那么就让下一个元素进窗口，然后继续判断：

此时3也进入窗口了，值还是小于7，那么就继续进窗口，那么这里我直接快进到最佳位置（就是大

于等于目标值7的位置）：

此时判断一下，已经大于目标值了，所以这里判断成功要出窗口了，但是这里还要更新一下结果

（根据题目看是什么时候判断结果，有些题目是进窗口之前更新结果，有些则是出窗口的时候判断

结果）：

此时就要出窗口了，那么就让left右移：

此时sum小于目标值，那么就进窗口right++：

此时大于目标值，所以先更新结果，长度依旧是4，那么不变，然后就可以出窗口了，left++：

left++完，滑出窗口时也要让sum减掉之前指向的值，所以现在和等于7，那么符合要求，就更新结

果长度变为3.此时就继续出窗口，left++：

此时出窗口之后和变为6，那么就小于7了，就进窗口，right++：

此时进完窗口后，结果就变为9，是大于7的，那么就更新结果冷，还是等于3，那么就出窗口

left++：

此时出窗口之后，和变为7，那么是符合要求的，那么就更新结果，长度就变为2，此时就继续出窗

口：

此时和就小于7了，就不符合了，那么就进窗口，right++：

但是此时没有下一个元素了，那么滑动窗口就结束了，此时这个len就是我们的最后结果了

这就是整个滑动窗口的整个过程。

那么滑动窗口的正确性是什么，就是因为单调性，当你找到一个值的时候就算大于等于7的边界时

就没必要往后移了，因为一定大于7了，长度还增加了，所以一定不是最后的结果，所以此时只要

出窗口，缩小长度看看是否继续符合。

时间复杂度：虽然之后的代码是两层循环，但是其实他就遍历了一遍数组，实则时间复杂度就是O(n).

3.代码展示：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n=nums.size();
        int sum=0;
        int len=INT_MAX;//因为如果定义成0的话找最小长度，那么一直就是0最小了，所以定义大一点的值
        for(int left=0,right=0;right<n;right++){
            sum+=nums[right];//进窗口
            while(sum>=target)//判断
            {
                len=min(len,right-left+1);//更新结果
                sum-=nums[left];
                left++;//出窗口
            }
        }
        if(len==INT_MAX){
            return 0;
        }else{
            return len;
        }
    }
};