【滑动窗口】LeetCode 209题解 | 长度最小的子数组

前言：滑动窗口

有关于滑动窗口的5个知识点：

1. 什么是滑动窗口？—— 同向双指针
2. 什么时候用滑动窗口？—— 单调性
3. 为什么能够用滑动窗口正确解决问题？—— 利用单调性，规避了很多没必要的枚举行为。
4. 滑动窗口的时间复杂度？—— O(n)
5. 如何书写滑动窗口的代码？

一、题目链接

长度最小的子数组

二、题目

三、算法原理

解法一：暴力枚举

枚举出所有的子数组求和，枚举出一个结果的同时更新最小长度。

时间复杂度是O(n^3)：

1. 枚举子数组：确定子数组左右区间，O(n^2)
2. 求和：遍历左右区间内的所有元素求和，O(n)

暴力枚举优化为O(n^2)：定义完left后，定义变量sum计算right右移过程中区间内的所有元素的和。避免再遍历一遍求和。sum初始化为0，sum直接继续加即可。例如：

---

"正整数"是一个优化的方向。

对于 ≥ 0 的数，作加法运算的单调性性质：加一起求和的数越多，那么和越大。

利用这个单调性作优化：先模拟优化后的暴力枚举方法。

前面的枚举过程：

当枚举出 sum >= target 的子数组，更新长度 len。按照暴力枚举，right会继续向后找符合要求的子数组。虽然sum >= target，但是len在变大，与题中要求是找长度最小的不符：

规律1：找到一个结果后，right后面的元素一定不是最终结果，right不用向后枚举了。

接着再依次固定left，依据暴力枚举，right需回退再枚举：

当枚举到下图，发现right不用回退且sum不用挨个相加，直接用上一个sum减去上一个固定的left值即可：

规律2：当找到一个结果后，left右移一步且right不用回退，此时的区间内的sum <= target。为什么right不用回退？若right回退，计算sum的过程中，还会在上一次停止的地方停止或继续向后走。

根据规律1、2，得出解法二：

解法二：利用单调性，用滑动窗口解决问题

上面的分析得出，left与right两个指针都是向右移动的，即同向双指针，也就是滑动窗口。滑动窗口维护的是一个区间里的信息，本题里维护的就是一段区间里的和。在两个指针都从左向右移动的过程中，很像一个窗口在数组里从左向右滑动。

---

那么怎么用滑动窗口解决问题？

1. 初始化滑动窗口的左右端点：left = 0, right = 0;
2. 进窗口
3. 判断
   出窗口

2、3步骤循环。这一循环里还有"更新结果"一步，这一步在哪执行要具体分析，可能在进窗口时更新，可能在出窗口前更新，还可能在整个判断步骤结束后更新。

---

为什么出窗口后还要再判断？因为出窗口后只出了一个元素，这个窗口区间内的所有元素之和可能还是≥target的。

用滑动窗口模拟过程：

right到最后是循环终止的条件，最终结果就是最短长度。

---

分析滑动窗口的时间复杂度

进窗口、判断的整个过程有个循环，判断过程也有个循环，循环嵌套，那么时间复杂度是O(n^2)吗？这里不要看代码分析时间复杂度。要依据实际情况分析：每一步操作仅让right/left向后移动一步，直到让right移动到最后为止。

最差情况：right先一步一步移动到最后一个元素停止，left再一步一步移动到最后一个元素停止，最后right再移动到最后循环结束，因此总的操作数：n + n == 2n，时间复杂度是O(n)。

四、编写代码

注意初始化变量len时，若把len初始化为0，因为求min，所以最后结果一定都是0。因此就要把len初始化大一点。

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size(), len = INT_MAX;for (int left = 0, right = 0, sum = 0; right < n; ++right){sum += nums[right];// 进窗口while (sum >= target)// 判断{len = min(len, right - left + 1);// 更新结果sum -= nums[left++];// 出窗口}}return len == INT_MAX ? 0 : len;}
};