leetcode209. 长度最小的子数组

方法一

暴力，时间复杂度O(n^2)

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int ans=INT_MAX;
        int n=nums.size();
        if(n==0)return 0;
        for(int i=0;i<n;i++){
            int sum=0;
            for(int j=i;j<n;j++){
                sum+=nums[j];
                if(sum>=target){
                    ans=min(ans,j-i+1);
                    break;
                }
            }
        }
        return ans==INT_MAX?0:ans;
    }
};

方法二

滑动窗口，时间复杂度O(n)

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int ans=INT_MAX;
        int n=nums.size();
        if(n==0)return 0;
        int sum =0,l=0,r=0;
        while(r<n){
            sum+=nums[r];
            while(sum>=target){
                if(sum>=target)ans=min(ans,r-l+1);
                sum-=nums[l++];
            }
            r++;
        }
        return ans==INT_MAX?0:ans;
    }
};