# 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).

## # 解题方法

### # 虫取法

``````class Solution:
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
N = len(nums)
l, r = 0, 0
csum = 0
res = float('inf')
while r < N:
csum += nums[r]
while csum >= s:
res = min(res, r - l + 1)
csum -= nums[l]
l += 1
r += 1
return res if res != float('inf') else 0
``````

C++代码如下：

``````class Solution {
public:
// O(N) using two pointer
int minSubArrayLen(int s, vector<int>& nums) {
const int N = nums.size();
if (N == 0) return 0;
int left = 0, right = 0;
// sum = sum[left, right)
long long sum = 0;
int res = INT_MAX;
while (right <= N) {
if (sum >= s) {
res = min(res, right - left);
sum -= nums[left++];
} else {
sum += nums[right++];
}
}
return res == INT_MAX ? 0 : res;
}
};
``````

### # 二分查找

``````class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
const int N = nums.size();
vector<int> sums;
sums.push_back(0);
for (int i = 0; i < N; ++i) {
sums.push_back(nums[i] + sums.back());
}
int res = INT_MAX;
for (int i = 1; i <= N; ++i) {
int target = sums[i] - s;
if (target < 0) continue;
auto pos = binary_search(sums, target);
if (pos > N) continue;
if (sums[i] - sums[pos] == s)
res = min(res, i - pos);
else if (sums[i] - sums[pos] < s)
res = min(res, i - pos + 1);
}
return res == INT_MAX ? 0 : res;
}
int binary_search(vector<int>& sums, int target) {
const int N = sums.size();
// [l, r)
int l = 0, r = N;
while (l < r) {
int mid = l + (r - l) / 2;
if (sums[mid] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
};
``````

## # 日期

2018 年 10 月 15 日 —— 美好的周一怎么会出现雾霾呢？ 2019 年 1 月 11 日 —— 小光棍节？