🔢 209.长度最小的数组

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

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

思路

基本思想

为了求出连续的子数组，首先想到的就是将数组排序，从最大的一直累加，直到超过target，说明找到了连续的子数组，但是题意并不是如此，前提不能改变数组中元素的位置，只能从原数组中找出一个连续的子数组

为了不变更数组中元素的位置，只能一次从每一个元素为起点，然后向后累加，但是这又会用到一个双层循环，为了减小时间复杂度，一旦超过target，代表找到了一个连续的子数组，此时判断当前子数组的长度是否小于当前记录的最小长度，是的话就更新

更新完成之后，需要从下一个元素为起点开始遍历，细想一下会发现元素之间有重叠的部分，例如以[1,2,3,4,5]为例，target=10，1+2+3+4已经大于等于10，此时变换起点，以2 为起点，会发现2+3+4这一部分已经计算过了，不需要重复计算，所以只需要简单的去掉1即可，在图中就是[3,1,2]是重复的部分

并且一次不只是去掉一个元素，一直删除元素，直到当前的和小于target才更换起点，因为删除元素的过程中如果还是大于等于target，那么最小连续子数组的长度就会更新。

此时需要记录起点的位置，方便计算超过target之后，连续子数组的长度，最后需要注意，只有当sum大于等于target时，才会更新min，所以 min有可能一直不会更新，所以需要注意返回最终的结果时还需要判断一次

执行流程

1. sum一直累加

2. 当sum大于target时开始删除起点

   1. 删除起点之后，最小连续子数组的长度变小，则更新
   2. sum减小
   3. 重复上面的步骤，直到sum小于target

3. 转到1

4. 返回结果时需要判断min是否更新

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int start=0;
        int sum=0;
        //保证min一定可以更新
        int min=INT_MAX;
        for(int i=0;i<nums.size();++i){
            sum+=nums[i];
            //一旦超过target，一直删除，直到小于target
            while(sum>=target){
                min=(i-start)+1<min?(i-start)+1:min;
                //删除一个元素就更换一下起点
                sum-=nums[start++];
            }
            //sum小于target时，sum继续累加
        }
        return min==INT_MAX?0:min;
    }
};

总结

利用了滑动窗口的思想，只要sum超过target，那么就更新min的值，并且删除起点，代表从新节点出发，只要sum大于target，就一直删除起点，只要sum小于target，就一直累加sum