leetcode 209. 长度最小的子数组

题目链接：leetcode 209

1.题目

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

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

2.示例

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

2）示例 2：
输入：target = 4, nums = [1,4,4]
输出：1

3）示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

4）数据范围：
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

3.分析

首先使用前缀和数组进行记录，对于固定区间某个右端点st2,当sum[st2]-sum[st1]>target时，说明区间长度可以缩小，st1++,当sum[st2]-sum[st1]<target，说明区间长度需要增加才能满足要求，st1++，同时对于大于上一时刻st2_last的st2_now,st1_last已经是满足sum[st2]-sum[st1]>target的最大st1了，st1之前的不需要遍历，时间复杂度为O(n)

4.代码

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {//O(n)int sum[100010];for(int i=0;i<nums.size();i++)sum[i+1]=sum[i]+nums[i];int st1=0,st2=1,ans=nums.size();if(sum[nums.size()]<target) return 0;while(st1<st2&&st2<=nums.size()){while(sum[st2]-sum[st1]>target&&st1+1<st2)st1++;while(sum[st2]-sum[st1]<target&&st1-1>=0)st1--;if(sum[st2]-sum[st1]>=target)ans=min(ans,st2-st1);st2++;}return ans;}
};