题解 | #牛群保卫战#

知识点

双指针

思路

由题意，我们需要找的是最短的连续区间，所以可以使用双指针来维护这段区间。

假设i为区间左端，j为区间右端。我们先假设i处于0，j也处于0，然后右移j。

当区间的和sum>=target时，我们可以尝试右移i，如果能保持右移后的i~j区间和sum’仍大于等于target，则成功缩短了区间的长度。

完整代码c++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型vector 
     * @return int整型
     */
    int findMinSubarrayLength(int target, vector<int>& nums) {
        // write code here
        int i=0;
        int sum=nums[0];//初始化sum
        int ans=nums.size()+1;//初始化答案为区间存在下不可能取到的一个大值
        for(int j=0;j<nums.size();j++)
        {
            if(j!=0) sum+=nums[j];//忽略第一个的情况
           
             while (sum-nums[i]>=target)//若缩短后sum仍合法，则可以缩
             {sum-=nums[i],i++;
              
             }
            if(sum>=target)ans=min(ans,j-i+1);//维护最小区间长
             
        }
        if(ans==nums.size()+1)return 0;//若答案未被更新，说明所求区间不存在
        return ans;
    }
};

注意此题的测试点强度较弱。