**Description:**

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

**Boundary:**

- if sum of
**nums()** < s, there is no proper subarray.

**Algorithm:**

**My first solution:**

Just gets sum of the 0-th element to the k-th element:** sum[k+1]**. Then the sum of the i-th element to the j-th element will be** sum[j] – sum[i]**.

Then traverse i from 0 to **nums.size() ** to find the start of the subarray.

Then traverse j from i+1 to **nums.size() + 1** to find the end of the subarray.

Find the min length, and replace the older one if shorter.

However, the timing is not good.

**Whether to get sum initially?** I remember some problems about subarray which got sum initially. However, we don’t need it in this problem.

**Second solution ( O(n) ):**

Count from the 0-th element and find **sum[j] > s** with min **j**.

Gradually shorten the subarray by subtracting the element at the beginning of the subarray until **sum[j] < s.**

Extend at the tail and shorten at the beginning.

**Code:**

class Solution {

public:

int minSubArrayLen(int s, vector<int>& nums) {

int begin = 0;

int end = 0;

int n = nums.size();

int sum = 0;

int length = INT_MAX;

while (end < n)

{

sum += nums[end++];

while (sum >= s)

{

length = min(end – begin,length);

sum -= nums[begin++];

}

}

return length == INT_MAX ? 0: length;

}

};

**Explanation:**

Well, you may wonder how can it be `O(n)`

since it contains an inner `while`

loop. Well, the key is that the `while`

loop executes at most once for each starting position `start`

. Then `start`

is increased by `1`

and the `while`

loop moves to the next element. Thus the inner `while`

loop runs at most `O(n)`

times during the whole `for`

loop from `0`

to `n - 1`

. Thus both the `for`

loop and `while`

loop has `O(n)`

time complexity in total and the overall running time is `O(n)`

. (Cited from: https://discuss.leetcode.com/topic/17063/4ms-o-n-8ms-o-nlogn-c)