双指针｜长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

输入：target = 4, nums = [1,4,4]
输出：1

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

进阶：如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

错误解法：

思路为设置快慢双指针fast和slow，slow用来记录连续长度，fast用来迭代索引。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int slow=1,fast=1;
        int tmp=nums[0];
        while(fast<=nums.size()){
            if(tmp<target){
                tmp+=nums[fast];
                slow++;
                fast++;
            }
            else if(tmp>target){
                tmp=nums[fast];
                slow=1;
                fast++;
            }
            else return slow;
        }
        return 0;
    }
};

代入案例计算得到的结果看似正确，但是在运行时依然报错：

错误的思路在于，这里试图用slow来记录长度，并且在tmp大于target时直接将长度恢复到1.然而实际上可能复合题意的字段并不是从值超出的索引处开始的。

如对target=10,nums=[3,4,1,5,4,9],按照代码思路，则在5时tmp=13>10，直接将tmp赋值4，再对后面进行逐个相加，就会发现没有符合要求的字段，但其实是因为忽视了中间的部分。这一误区主要是受前面做过用快慢指针寻找连续的1字段最长长度影响，可以不是1直接跳过并且重新开始，但是这并不适用于和的寻找。

正确解法：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int size = nums.size(), sum = 0, minn = size + 1, l = 0, r = 0; //l和r分别表示两端
        while(r < size){
            sum += nums[r];
            while(sum >= target){
                minn = min(minn, r - l + 1);
                sum -= nums[l++]; //相当于把截取部分左端右移一位
            }
            r++;
        }
        return minn == size + 1 ? 0 : minn; 
        //满足?条件取前者，不满足取后者。这里minn等于size+1，说明没有经过while，sum一直小于target
    }
};

将双指针设置为目标字段的左右端left和right，从左到右依次相加，当sum大于目标值时，再从左端依次删去，最后对比得到所寻字段。

双指针的两个具体应用场景：滑动窗口；快慢指针。