Minimum Size Subarray Sum

Given an array ofnpositive integers and a positive integers, 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).

Analysis

Two Pointers

设定左右指针，一般的想法是固定starting index，但是这里其实固定ending index，反过来内层循环starting index更方便。每个循环nums[j]加入到sum中，如果满足sum >= s，就可以修改starting index，让sum -= nums[i]，同时记录比较最小的区间长度，直到内层循环让sum >= s的条件不再满足。外层循环的条件则是j遍历到达数组的末尾。

• Time complexity: O(n)

Each element can be visited atmost twice, once by the right pointer(j) and (atmost)once by the left pointer (i).

• Space complexity: O(1)

类似题扩展：

Minimum Size Subarray Sum

Minimum Window Substring

Longest Substring Without Repeating Characters

Binary Search

https://leetcode.com/problems/minimum-size-subarray-sum/discuss/59103/Two-AC-solutions-in-Java-with-time-complexity-of-N-and-NLogN-with-explanation

@ lx223: As to NLogN solution, logN immediately reminds you of binary search. In this case, you cannot sort as the current order actually matters. How does one get an ordered array then? 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.

虽然数组nums[]本身没有排序过，但是因为元素均为正数，前缀和prefix sum其实是一个严格递增的数组，因此确定了starting index之后，可以用binary search寻找ending index。

Time: O(nlogn) - outer loop O(n), binary search in each loop O(logn), thus O(n * logn)

Space O(n) - additional prefix sum array O(n)

Solution

Two Pointers - Time: O(n), Space O(1)

@lacfo: It seems like that two while loops give O(N^2). But actually, for every j, i is not starting from 0. Pointer i will not go back, so in the worst case, pointer j moves forward n times and pointer i also moves forward n times.

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

Binary Search - Time: O(nlogn), Space O(n)

class Solution {
    public int minSubArrayLen(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;
    }
}

Reference

https://leetcode.com/problems/minimum-size-subarray-sum/solution/

https://leetcode.com/problems/minimum-size-subarray-sum/discuss/59078/Accepted-clean-Java-O(n)-solution-(two-pointers\)

https://leetcode.com/problems/minimum-size-subarray-sum/discuss/59110/O(N)-template-for-Minimum-Size-Subarray-Sum-and-Minimum-Window-Substring-and-Longest-Substring-Without-Repeating-Characters

https://leetcode.com/problems/minimum-size-subarray-sum/discuss/59103/Two-AC-solutions-in-Java-with-time-complexity-of-N-and-NLogN-with-explanation