leetcode -- 209 长度最小的子数组[滑动窗口/c++]

原题链接：209. 长度最小的子数组 - 力扣（LeetCode）

算法原理：

滑动窗口其实就是同向双指针，因为计算结果的单调性，在符合条件的情况下，左右指针不必往回回溯，而实现优化的效果。

滑动窗口分为4步（构成一个循环）

1. 进窗口（对right指针指向的数据进行处理）

2.判断（判断的作用是决定是否要进行出窗口操作）

3.出窗口（一般是移动left指针）

4.更新状态（可能在出窗口前，也可能在出窗口后，依情况而定）

这里的进出窗口针对的是数组中的元素，比如right++后指向的元素，就表示被放进了窗口。

为什么滑动窗口不会漏解？

理由一开始就说了，根据计算结果的单调性，省略掉的结果不影响最终值。

比如此题中，滑动窗口（双指针包围的数）内的数值和已经大于或等于目标值，此时right再++的话，len长度就更长了，题目要求返回长度最小的子数组长度，所以没有再让right++的必要，直接让left++，开始遍历下一个子数组。

注意，left++时，right不必重新回到left位置，只要让sum减去原本的left指向的值即可。因为我们是在一达到题目要求（大于等于目标值）的情况下就进行调整的，也就是出窗口操作，所以也不可能存在漏解的情况。

代码

此题更新状态需要用到left和right指针的相对位置，所以是在出窗口之前更新状态

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
int len = INT_MAX,n = nums.size(),sum =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++];//出窗口
    }
}
return len == INT_MAX?0:len;
    }
};