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

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

### # Solution

Approach 1: Two pointers (sliding window).

Approach 2: Binary search.

### # Code (Python)

Approach 1:

``````    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
# O(N): sliding window
min_len = float('inf')
total = 0
left = 0
for right in range(len(nums)):
total += nums[right]
if total < s:
continue
while left + 1 <= right and total - nums[left] >= s:
total -= nums[left]
left += 1
min_len = min(min_len, right - left + 1)

return min_len if min_len < float('inf') else 0
``````

Approach 2:

``````    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
# O(NlogN): binary search
if sum(nums) < s:
return 0

lo, hi = 1, len(nums)
# find first(lowest) item such that has_sum_>=_s(item) == True
while lo < hi:
mid = (lo + hi) // 2
if self._has_sum(mid, nums, s):
hi = mid
else:
lo = mid + 1
return lo

def _has_sum(self, length, nums, target):
total = sum(nums[:length])
if total >= target:
return True
for i in range(length, len(nums)):
total += nums[i]
total -= nums[i-length]
if total >= target:
return True
return False
``````

### # Code (C++)

Approach 1:

``````// Two pointers.
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int tail = 0;
int sum = 0;
int max = 0;
int minLen = 0;
while (sum >= s || tail < nums.size())
{
if (sum < s)
{
sum += nums[tail];
tail++;
}
else
{
if (minLen == 0 || minLen > tail - head)
}
}
return minLen;
}
};
``````

Approach 2:

``````// Binary search.
class Solution {
private:
int binarySearch(int target, int sum[], int head, int tail) {
{
if (sum[mid] < target)
else if (sum[mid] > target)
tail = mid - 1;
else
return mid;
}
}
public:
int minSubArrayLen(int s, vector<int>& nums) {
int n = nums.size();
if (n == 0 || s == 0)
return 0;
int sum[n];
sum[0] = nums[0];
for (int i = 1; i < n; ++i)
{
sum[i] = sum[i-1] + nums[i];
}
int minLen = 0;