Minimum Size Subarray Sum

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

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

More practice:

If you have figured out theO(n) solution, try coding another solution of which the time complexity isO(nlogn).

Solution:

Use a sum array to record the sums from the first number to current number. Use binary search to find if there exist a previous sum that is equal or smaller than current sum - target (last value <= sum - target). If there is, calculate length, and use Math.min to get the size of the desired subarray. Binary search can be used to search the sum array as it is ascending due to no negative values.

Note: the length of a subarray is equal to index current - previous. However, when the previous index is 0, the length must +1.

public int minSubArrayLen(int s, int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int[] sums = new int[nums.length];
    int sum = 0,
        min = Integer.MAX_VALUE;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] >= s) {
            return 1;
        }
        sum += nums[i];
        sums[i] = sum;
        if (sum == s) {
            min = Math.min(min, i + 1);
        } else if (i > 0 && sum > s) {
            int subsize = binarySearch(sums, i - 1, sum - s);
            min = subsize == -1 ? Math.min(min, i) : Math.min(min, i - subsize);
        }
    }
    if (sum < s) {
        return 0;
    }
    return min;
}
private int binarySearch(int[] sums, int endIndex, int target) {
    int left  = 0,
        right = endIndex,
        index = -1;
    while (left < right){
        int mid = left + (right - left) / 2;
        if (sums[mid] <= target) {
            index = mid;
            left  = mid + 1;
        } else if (sums[mid] > target) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return index;
}