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

Have you met this question in a real interview?

Yes

Example

Given the array[2,3,1,2,4,3]and s =7, the subarray[4,3]has the minimal length under the problem constraint.

前向型双指针，保持一个第一个指针到第二个指针的窗口，通过o(1)时间判断窗口内的和是否大于等于target

注意窗口条件是while 不满足， 所以要包括进第一个满足的情况

public class Solution {
    /*
     * @param nums: an array of integers
     * @param s: An integer
     * @return: an integer representing the minimum size of subarray
     */
    public int minimumSize(int[] nums, int s) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int ans = Integer.MAX_VALUE;
        int i = 0;
        int j = 0;
        int sum = 0;
        for (i = 0; i < nums.length; i++) {
            while (j < nums.length && sum < s) {
                sum += nums[j];
                j++;
            }

            if (sum >= s) {
                ans = Math.min(ans, j - i);
            }

            sum -= nums[i];
        }
        if (ans == Integer.MAX_VALUE) {
            return -1;
        }
        return ans;
    }
}