Description

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

Example

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

Solution

1. 两个指针， O(n)，left到right之间的subarray sum<s时right指针往前走，找到第一个sum>=s的情况返回left和right的距离，然后left往前走一步，right回到起点即left的位置 没有符合条件的subarray的corner case返回0

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int left = 0;
        int right = 0;
        int sum = 0;
        int min = Integer.MAX_VALUE;

        while (right < nums.length) {
            sum = nums[left];
            while (sum < s && right + 1 < nums.length) {
                sum += nums[++right];
            }
            if (sum >= s) {
                min = Math.min(min, right - left + 1);
            }
            right = ++left;
        }

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

cleaner version: 上面的方法中，找到第一个sum>=s的subarray后left++， right返回left的位置可以优化一下为：right不动，left往前走，走到sum<s为止，再重新开始移动right，这样省去了长度从0开始找的过程

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int left = 0;
        int right = 0;
        int sum = 0;
        int min = Integer.MAX_VALUE;

        while (right < nums.length) {
            sum += nums[right++];

            while (sum >= s) {
                min = Math.min(min, right - left);
                sum -= nums[left++];
            }
        }

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

1. O(nlogn)的方法，先求出一个sum数组，sum[i]表示0到i的subarray的sum。遍历sum，对i到length-1的数二分查找第一个值>=s的元素