209.长度最小的子数组 - Java 滑动窗口

原题链接：https://leetcode.cn/problems/minimum-size-subarray-sum/

题解

维护一个滑动窗口，并维持以下原则：

• right一直向右扩展至sum>=target
• left一直向右伸缩至sum<target

由于right扩展后的子数组不一定是最优解，在left伸缩后可能仍然有sum>=target，right固定时的最优解应为：当前right不变，left伸缩到满足sum>=target的最右边时的长度

所以我们每次在left伸缩时再根据sum是否大于等于target更新min

时间复杂度：O(N)；
空间复杂度：O(1)；

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int sum=nums[0],min=999999;
        int left=0,right=0;

        while(right<nums.length-1){
            while(sum<target&&right+1<nums.length){
                right++;
                sum+=nums[right];
            }
            while(sum>=target&&left<nums.length){
                if(min>right-left+1)min=right-left+1;
                sum-=nums[left];
                left++;
            }
        }
        if(min==999999)return 0;
        return min;

    }
}