目录
1.题目
想要介绍一个算法，没有具体的例子来说算法是非常抽象的，算法是一种思想，因而为了介绍有关滑动窗口的概念，用下面例子来做相关介绍。
题目链接：LINK
看到这个题目我们先不论什么是“滑动窗口”这种算法，我们先从最简单的暴力求解来思考，顺着暴力求解的思路一步一步优化，最终达到“滑动窗口”的算法效果。
2.暴力求解
2.1暴力求解思路：
两个指针，一个left，一个right，加上left和right之间的所有数跟target进行比较，找到最小的len即可。
我们以上面的题目为例子，以题目中示例1为具体的操作对象：
left和right的组合共有36种情况，如下图所示：
2.2时间复杂度是多少？
答：left和right两层循环并且求sum时候需要再遍历一次，所以是N^3
当然这种代码很挫哈，为了提高效率，我们引出“滑动窗口”这一算法思想。
3.暴力求解的优化
滑动窗口是一种高效的算法，说白了也是从暴力求解的思路中优化过来的，所以我们一步一步来优化该暴力求解思路，来更加高效。
3.1固定left的情况下，优化right的次数。
在同一个left的情况下，很多时候right是多余的。比如说2 + 3 + 1 + 2 = 8早就超过target = 7了，暴力求解还在继续向后加…这很多余。
3.2sum求值优化
求和的时候，每次left和right变的情况下都要重新计算，十分耗费性能。我们想是不是可以利用一下上一次的sum值来求这次的sum值？
经过优化，这样就基本接近滑动窗口算法了。但还不是。这时的时间复杂度是O(N^2)
在本题中大概优化到下面效果：
大概就是下面的代码：
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int ret = INT_MAX;int n = nums.size();// 枚举出所有满⾜和⼤于等于 target 的⼦数组[start, end]// 由于是取到最⼩，因此枚举的过程中要尽量让数组的⻓度最⼩// 枚举开始位置for (int start = 0; start < n; start++){int sum = 0; // 记录从这个位置开始的连续数组的和// 寻找结束位置for (int end = start; end < n; end++){sum += nums[end]; // 将当前位置加上if (sum >= target) // 当这段区间内的和满⾜条件时{// 更新结果，start 开头的最短区间已经找到ret = min(ret, end - start + 1);break;}}}// 返回最后结果return ret == INT_MAX ? 0 : ret;}
};
不用怀疑，力扣过不了哈。
3.3不同组之间left与right包含关系的优化
这个是什么意思呢？
嗯…经过上面所说的两步之后，我们就发现以上面的题目来举例，暴力求解就可以达到下面这种优化效果：
当然，上面超出时间限制截图告诉我们，继续优化…
但是我们发现一个问题，比如拿下面的例子来说(看蓝色框)
放大一点：
就是这种不满足的包含情况下也可以优化掉。
下面是真正的滑动窗口优化图：
4.滑动窗口算法
4.1概念
4.2应用场景
具有一定单调性题目，比如在本节博客的举的这道题种，从left到right不断加就是一种单增关系。
4.3使用
滑动窗口的大体使用步骤是什么呢？
- 1.left，right
- 2.进窗口
- 3.判断
- 出窗口
- 更新结果
注：①2、3两步是循环；②本步骤只是大体步骤；
比如说，在本例子中，这个步骤就可以具体为：
- 1.先让left = 0，right = 0；
- 2.进窗口，sum +=2；
- 3.判断sum < target；
- 4.所以继续进窗口，让right = 1，sum+=3；
- 5.继续判断，sum = 5 < target
- 6.继续进窗口，right = 2，sum+=1
- 7.继续判断，sum = 6 < target
- 8.继续进窗口，right = 3，sum+=2
- 9.继续判断，sum = 8 > target
- 10.满足条件，出窗口
- 11.left++，left = 1，sum-=2
- 12.判断sum = 6 < target
- 13.right++，right = 4，sum+=4
- 14.判断sum = 10 > target
- 。。。
4.4正确性
滑动窗口算法对吗？是正确的。
因为只是在暴力求解的基础上去掉了一些不必要的计算过程。
4.5时间复杂度
对于上面那道题来说，暴力求解是O(N^3)，但是滑动窗口是O(N)
5.题解代码示例
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int ret = INT_MAX;int n = nums.size();int sum = 0;for(int left = 0,right = 0;right < n;right++){sum+=nums[right];//进窗口while(sum>=target)//判断{ret = min(ret,right - left + 1);sum-=nums[left];//出窗口left++;//持续判断}}// 返回最后结果return ret == INT_MAX ? 0 : ret;}
};
EOF
