LeetCode-209-长度最小的子数组

题目

思路

1. 第一反应是用二维数组存dp从i到j的总和，如果等于target的时候就算长度，只记录短的那条，但感觉数据规模上好像过不了。一维的话尝试了一下用前缀和解决。
2. 但是没有想到用前缀和做二分搜索…连续子数组大部分要使用滑动窗口或者前缀和

代码

    public int minSubArrayLen(int target, int[] nums) {
    
        int left = 0,right = 0;
        int ans = Integer.MAX_VALUE;
        //维护一个和sum
        int sum=0;
        while(right<nums.length){
    
            sum+=nums[right];
            //如果加上end后>=target了
            //开始左移start
            while(sum>=target){
    
                ans = Math.min(ans,right-left+1);
                sum-=nums[left];
                left++;
            }
            right++;
        }
        return  ans == Integer.MAX_VALUE ? 0 : ans;
    }