长度最小的子数组

题目

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

找出该数组中满足其总和大于等于 target 的长度最小的 连续

子数组

 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

解析

1.正整数数组，目标值target,找出一个连续区间，使得这个区间大于等于目标值（最短的长度返回）

示例 1：

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

示例 2：

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

示例 3：

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

解法

    解法一

暴力枚举出所有的子数组的和-->优化，双指针法 left right 两个指针同时遍历 

具体步骤

left从最左边开始，right从下个数字开始，right遍历一个数字，就和left相加，返回值给到sum，判断sum和target的值，如果sum小于target，则继续遍历，如果大于则停止 此时长度位  len=right-left的距离;

解法二

利用单调性   使用“同向双指针”（滑动窗口）的来优化

怎么用：1.left=0,right=0

               2.进窗口

               3.判断     出窗口    ------>（判断成立 更新结果）（类似于暴力枚举)

时间复杂度n+n-->2n  o(n)

代码

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

以上内容只是小编的一点间接，如有错误或者不全之处请及时指出，谢谢大家的关注