# 209. Minimum Size Subarray Sum (1)

[Link](https://www.cnblogs.com/grandyang/p/5336668.html)

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

**Example:**&#x20;

```
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:**&#x49;f you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).&#x20;

**Solution**

**O(n) solution**\
Two pointers

```
 public int minSubArrayLen(int s, int[] nums) {
        int len = nums.length;
        int minLen = Integer.MAX_VALUE;
        int sum = 0, end = 0, start = 0;
        while(end < nums.length){
            sum += nums[end];
            while(sum >= s && start < nums.length){
                minLen = Math.min(end-start+1, minLen);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
```

Follow up: &#x20;

**O(nlogn):** 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.

```java
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;
}
```
