## 题目描述：

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

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

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

## 解题思路：

O(n)解法：滑动窗口法，使用两个下标start和end标识窗口（子数组）的左右边界

O(nlogn)解法：二分枚举答案，每次判断的时间复杂度为O(n)

## Python代码：

O(n)版本`I`

``````class Solution:
# @param {integer} s
# @param {integer[]} nums
# @return {integer}
def minSubArrayLen(self, s, nums):
size = len(nums)
start, end, sum = 0, 0, 0
bestAns = size + 1
while end < size:
while end < size and sum < s:
sum += nums[end]
end += 1
while start < end and sum >= s:
bestAns = min(bestAns, end - start)
sum -= nums[start]
start += 1
return [0, bestAns][bestAns <= size]
``````

O(n)版本`II`

``````class Solution:
# @param {integer} s
# @param {integer[]} nums
# @return {integer}
def minSubArrayLen(self, s, nums):
size = len(nums)
start, end, sum = 0, 0, 0
bestAns = size + 1
while True:
if sum < s:
if end >= size:
break
sum += nums[end]
end += 1
else:
if start > end:
break
bestAns = min(end - start, bestAns)
sum -= nums[start]
start += 1
return [0, bestAns][bestAns <= size]
``````

O(nlogn)版本：

``````class Solution:
# @param {integer} s
# @param {integer[]} nums
# @return {integer}
def minSubArrayLen(self, s, nums):
size = len(nums)
left, right = 0, size
bestAns = 0
while left <= right:
mid = (left + right) / 2
if self.solve(mid, s, nums):
bestAns = mid
right = mid - 1
else:
left = mid + 1
return bestAns

def solve(self, l, s, nums):
sums = 0
for x in range(len(nums)):
sums += nums[x]
if x >= l:
sums -= nums[x - l]
if sums >= s:
return True
return False
``````

Pingbacks已关闭。

1. coder 发布于 2015年11月23日 03:27 #

版本一14行多余

2. 在线疯狂 发布于 2015年11月23日 11:07 #

是的，感谢指正！已经去掉了这一行。 :D