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 -1 instead.
思路: 本题以two pointer的方法解可得O(N)的solution, 分别用两个pointer代表start和end元素, 当当前的和大于目标时, start向前移动, 当当前的和小于目标时, end向前移动. 时刻更新最小size值. 注意提前处理返回-1的情况.
class Solution:
# @param nums: a list of integers
# @param s: an integer
# @return: an integer representing the minimum size of subarray
def minimumSize(self, nums, s):
# write your code here
if not nums or sum(nums)<s:
return -1
if nums[0] >= s:
return 1
else:
_min = len(nums)
start, end = 0, 0
cur = nums[0]
while end < len(nums):
if cur < s:
end += 1
if end<len(nums):
cur+=nums[end]
else:
if end-start+1<_min:
_min = end-start+1
start+=1
cur-=nums[start-1]
return _min
