C++ 优先算法 —— 长度最小的子数组（滑动窗口）
目录
题目：长度最小的子数组
1. 题目解析
2. 算法原理
Ⅰ. 暴力枚举
Ⅱ. 滑动窗口（同向双指针）
滑动窗口正确性
3. 代码实现
Ⅰ. 暴力枚举(会超时）
Ⅱ. 滑动窗口（同向双指针）
题目：长度最小的子数组
1. 题目解析
题目截图：
这里需要注意一些题目的细节问题，如下：
上面 [4,3] 这个子数组符合 ≥target 的条件且是最短的长度为 2，所以，结果输出为 2。
若是数组中的其中一个值作为子数组就能满足 ≥target 的，最小长度的子数组长度必定是1。
若数组中所有的值相加都是 ＜ target ，那么不存在符合条件的子数组（整个数组也算是数组的子数组），就返回0。
2. 算法原理
这道题有两种解法：
- 暴力枚举
- 滑动窗口（同向双指针）
Ⅰ. 暴力枚举
暴力枚举：这里就是枚举出所有的子数组之和，判断它是否满足要求。
这里还可以优化一下，优化成O（N²）：
题目中，已经强调是一个正整数数组，数组里面的元素全都是 ＞0 的，在做加法的时候，加的数越多，和就越大（单调性）。
这样就可以省去再从前到后遍历一遍子数组了，这里还可以再优化一下：
也就是sum符合结果时，再向后枚举都符合结果（正整数数组），但是len是递增的，不符合要求，后面不需考虑。
接着让 left 往后移动一位，让 right 回退到 left 的位置 ，继续枚举。
Ⅱ. 滑动窗口（同向双指针）
在暴力枚举最后的优化情况，还可以观察到一个优化的地方：
此时 right 就可以不动，没有必要再让 right 回退到 left 的位置遍历再计算这一小段的子数组的和了，只需要更新 sum 即可（让 sum 减去 left 上一次指向的元素）。
这样就可以用双指针来解决了，也就是：利用单调性，使用同向双指针（两个指针移动方向一致）来优化。
同向双指针也称作滑动窗口。
什么时候用滑动窗口呢？
也就是利用单调性的时候。当发现利用暴力解法的时候，两个指针都可以做到不回退，都向同一个方向移动的时候，此时就可以用滑动窗口（本质就是同向双指针）。
怎么用滑动窗口？
- 先初始化 left 和 right （左端点，右端点） left = 0 ， right = 0 （用它俩分别标记窗口的左右区间）
- 进窗口
- 判断： 根据判断是否出窗口
（其中2、3步是循环的）
进窗口，在这里就是right所指向的元素进入窗口，进入窗口之后，sum就要更新 。
接着再让right往后移动即可，再接着判断：
再重复操作
right再向后移动1位时：
此时，就可以更新以下结果了，这里结果就是len（子数组长度）。 
更新完结果之后，再出窗口，这里就是让left向右移动一位，出窗口时候还需要把sum更新一下：
出完窗口之后继续判断：
这时，又到了进窗口之后判断的操作了：
注意：出完窗口时候还要继续判断， 因为可能依旧是大于等于target，若满足，还需要更新结果再出窗口：
此时，又观察到，sum<target，不满足要求，继续进窗口：
判断，又满足了要求，再接着出窗口（重复上面的操作）：
判断，又得出sum>target，继续出窗口：
判断，不满足要求 ，继续让right向后移动（进窗口）：
但此时可以观察到，没有下一个元素了，这时让right指向的下一个元素就已经越界了，这时窗口就结束了。此时这个 len 就是最终结果。
所以，大方向分为三步：1. 进窗口 。2. 判断。3. 出窗口。
这里更新结果需要看题目要求：有的需要进窗口时更新，有的需要出窗口时更新，有的会在出窗口之后再更新。
滑动窗口正确性
虽然并没有把所有的情况都给枚举出来，但是已经直到接下来的情况是没有必要的行为，因此是利用单调性，规避了很多没有必要的枚举行为。
这里时间复杂度：根据实际情况是每一步操作仅仅会让 right 向右移动 1 位或 left 向右移动 1 位，直到 right 移动到最后的位置。这里最差的情况下，也就是 n+n -> 2n 次，所以就是 O(N)。
3. 代码实现
题目链接：长度最小的子数组
Ⅰ. 暴力枚举(会超时）
//代码实现
//时间复杂度：O(N²)
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int len = INT_MAX;
for(int left = 0; left < n; left++)
{
int sum = 0;
for (int right = left; right < n; right++)
{
sum += nums[right];
if(sum >= target)
{
len = min(len,right-left+1);
break;
}
}
}
return len==INT_MAX?0:len;
}
};
提交记录：（会超时）
Ⅱ. 滑动窗口（同向双指针）
//代码实现
//注意这里虽然有两个循环，但是要根据实际情况
//时间复杂度:O(N)
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n=nums.size(), sum=0,len=INT_MAX;
//sum标记维护窗口的和，len标记最终结果
for(int left = 0, right = 0; right < n; right++)
{
sum += nums[right]; //进窗口
while(sum >= target) //判断是否要出窗口,用while循环确保连续出窗口的情况
{
len = min(len, right - left + 1); //更新结果
sum -= nums[left++]; //出窗口
}
}
return len == INT_MAX ? 0 : len;
}
};
提交记录：
制作不易,若有不足之处或出问题的地方，请各位大佬多多指教 ，感谢大家的阅读支持！！! 