209. Minimum-Size-Subarray-Sum

difficulty: Medium

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Example:

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

注意，这个题目的一个重要假设是，所有的元素都是正数，因此 prefixSumArray 是单调递增的。

Method One

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int minimum = Integer.MAX_VALUE;
        int sum = 0;
        int left = 0;
​
        for(int i = 0; i < nums.length; i++ ) {
            int right = i;
            sum += nums[i];
            while(sum >= s) {
                minimum = Math.min( minimum, (right - left + 1) );
                sum -= nums[left];
                left += 1;
            }
        }
        
        return minimum == Integer.MAX_VALUE  ?  0 : minimum;
    }
}
​

第二次写，先写的是这样的

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int minSize = Integer.MAX_VALUE;
        int sum = 0;
        int left = 0;
        for(int right = 0; right < nums.length; right++) {
            if(sum < s) {
                sum += nums[right];
            }
            while(sum >= s) {
                minSize = Math.min(minSize, right - left + 1);
                sum -= nums[left];
                left +=1;
            }
        }

        return minSize == Integer.MAX_VALUE ? 0 : minSize;
    }
}

后面发现可以把 if(sum < s ) 拿掉，因为 while 保证了下一次一定 sum < s