9.《滑动窗口篇》---①长度最小的子数组(中等)

时间:2024-11-20 18:29:09

我们不能说一上来就知道这个题目用滑动窗口,然后就使用滑动窗口的方法来做这个题目。

首先我们想到的应该是暴力解法。

接着再优化为滑动窗口

由于数字都是 ≥ 0 的数。因此累加的数越多。和越大。

因此right往后遍历的时候。当发现sum > target 就可以不用再往右移动了。

此时left往右移动一位。

按照暴力枚举。right 还需要从新回到left的位置。再次计算累加和是否≥target。

而我们发现 (使用暴力解法的时候两个指针可以不会退。就可以用滑动窗口了)

此时只需要让sum-2 然后再次判断。就可以了。而right不用移动。

这就引入了滑动窗口。

利用单调性,+同向双指针。

滑动窗口的使用:

1. left = 0,right =0;

2.进窗口

3.判断

4.出窗口