> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/two_pointers/minimum_size_subarray_sum.md).

# Minimum Size Subarray Sum

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:** 

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

```java
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)

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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/two_pointers/minimum_size_subarray_sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.