Question:

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 0 instead.

For 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.

click to show more practice.

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

Thinking:

My method is to hold two pointers, one for current index and the other is for the start pointer. Once we find the sum is bigger than target, we increse the startIndex until its sum is smaller than target. Do it while find the minmun of the length.

But there is still more effienct way to solve this problem. We don’t need to reset the startIndex and sum, we just keep it. And it will be the O(n) solution. (Which called a minmum window method I suppose.)

What’s more, binary search is also valid for this problem. Since all elements are positive, the cumulative sum must be strictly increasing. Then, a subarray sum can expressed as the difference between two cumulative sum. Hence, given a start index for the cumulative sum array, the other end index can be searched using binary search.

Solution:

First version:

public int minSubArrayLen(int s, int[] nums) {
    int min = Integer.MAX_VALUE;
    boolean flag = false;
    int temp = 0;
    int startIndex = 0;

    for ( int i = 0; i < nums.length; i++ ){
         temp += nums[i];
         if (temp >= s){
             while (temp >= s){
                 flag = true;
                 temp -= nums[startIndex++];
             }
             int len = i - startIndex + 2;
             i = startIndex-1;
             if (len < min)
                 min = len;
             temp = 0;
         }

    }
    if (flag)
        return min;
    else
        return 0;
}

Revised version:

public int minSubArrayLen(int s, int[] nums) {
    int min = Integer.MAX_VALUE;
    boolean flag = false;
    int temp = 0;
    int startIndex = 0;

    for ( int i = 0; i < nums.length; i++ ){
         temp += nums[i];
         if (temp >= s){
             while (temp >= s){
                 flag = true;
                 temp -= nums[startIndex++];
             }
             int len = i - startIndex + 2;
             if (len < min)
                 min = len;
         }

    }
    if (flag)
        return min;
    else
        return 0;
}

Reference Code:(Including O(n) and O(nlgn))
Reference:https://leetcode.com/discuss/35378/solutions-java-with-time-complexity-nlogn-with-explanation

public int minSubArrayLen(int s, int[] nums) {
    return solveNLogN(s, nums);
}

private int solveN(int s, int[] nums) {
    int start = 0, end = 0, sum = 0, minLen = Integer.MAX_VALUE;
    while (end < nums.length) {
        while (end < nums.length && sum < s) sum += nums[end++];
        if (sum < s) break;
        while (start < end && sum >= s) sum -= nums[start++];
        if (end - start + 1 < minLen) minLen = end - start + 1;
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

private int solveNLogN(int s, int[] nums) {
    int[] sums = new int[nums.length + 1];
    for (int i = 1; i < sums.length; i++) sums[i] = sums[i - 1] + nums[i - 1];
    int minLen = Integer.MAX_VALUE;
    for (int i = 0; i < sums.length; i++) {
        int end = binarySearch(i + 1, sums.length - 1, sums[i] + s, sums);
        if (end == sums.length) break;
        if (end - i < minLen) minLen = end - i;
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

private int binarySearch(int lo, int hi, int key, int[] sums) {
    while (lo <= hi) {
       int mid = (lo + hi) / 2;
       if (sums[mid] >= key){
           hi = mid - 1;
       } else {
           lo = mid + 1;
       }
    }
    return lo;
}