LeetCode 209-长度最小的子数组-尺取法（双指针）

题目

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。

输入:

s = 7, a= [2,3,1,2,4,3]

输出:

2

解释: 子数组 [4,3]是该条件下的长度最小的连续子数组。

思路

算法思路如下

（1） 以s=t=sum=0初始化

（2）只要依然有sum<S，就不断将sum增加a[t]，并将t+1

（3） 如果（2）中无法满足sum>=S,则终止。否则，更新res=min(res,t-s)

（4）将sum-a[s]，s增加1后回到（2）

代码

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int sum=0;
        int n=nums.size();
        int res=n+1;
        int t1,t2;
        t1=0;t2=0;

    for(;;)
    {
                while(t2<n&&sum<s)
                {
                            sum+=nums[t2++];
                }
                if(sum<s) break;//跳出while的条件是t2>=n，即加完所有数字 sum还是小于s
                res=min(res,t2-t1);
                sum-=nums[t1++];//sum>s跳出while,t1向前挪一个
    }
        if(res>n) return 0;
        return res;
    }
};
           

小小心得

我一开始写的是for循环 for(int i=0;i<n;i++){...}

后来发现这样结果不对，限制了每次不管发生什么i都会加一。后来参考书上 for(;;) 不遇到意外就不走了 真是聪明啊！！