406. 和大于S的最小子数组
中文
English
给定一个由 n 个正整数组成的数组和一个正整数 s ，请找出该数组中满足其和 ≥ s 的最小长度子数组。如果无解，则返回 -1。
样例
样例 1:
输入: [2,3,1,2,4,3], s = 7
输出: 2
解释: 子数组 [4,3] 是该条件下的最小长度子数组。
样例 2:
输入: [1, 2, 3, 4, 5], s = 100
输出: -1
挑战
如果你已经完成了O(nlogn)时间复杂度的编程，请再试试 O(n)时间复杂度。
class Solution:
"""
@param nums: an array of integers
@param s: An integer
@return: an integer representing the minimum size of subarray
"""
def minimumSize2(self, nums, s):
# write your code here
ans = float('inf')
n = len(nums)
j = 0
s2 = 0
for i in range(n):
while j < n and s2 + nums[j] < s:
s2 += nums[j]
j += 1
if j == n:
break
ans = min(ans, j - i + 1)
# s2 += nums[j]
s2 -= nums[i]
return ans if ans != float('inf') else -1
def minimumSize(self, nums, s):
# write your code here
ans = float('inf')
n = len(nums)
j = 0
s2 = 0
for i in range(n):
while j < n and s2 < s:
s2 += nums[j]
j += 1
if s2 >= s:
ans = min(ans, j - i)
s2 -= nums[i]
return ans if ans != float('inf') else -1
同向双指针， 模版1是强化班侯卫东老师介绍的 模版2是高频班老顽童老师介绍的
# 模版1
class Solution:
"""
@param nums: an array of integers
@param s: An integer
@return: an integer representing the minimum size of subarray
"""
def minimumSize(self, nums, s):
# write your code here
left, right = 0, 0
n = len(nums)
target = s
addup = 0
ans = sys.maxsize
for left in range(n):
while right < n and addup < target:
addup += nums[right]
right += 1
if addup >= target: # 满足条件
ans = min(right - left, ans)
addup -= nums[left]
return -1 if ans == sys.maxsize else ans
# 模版2: 枚举右端点，左端点不回头
class Solution:
"""
@param nums: an array of integers
@param s: An integer
@return: an integer representing the minimum size of subarray
"""
def minimumSize(self, nums, s):
ans = sys.maxsize
left = 0
addup = 0
for right in range(len(nums)):
addup += nums[right]
while addup >= s:
ans = min(ans, right - left + 1)
addup -= nums[left]
left += 1
return ans if ans != sys.maxsize else -1