LeetCode刷题DAY 33：长度最小的子数组
难度：中等 关键词：前缀和+二分查找、双指针
⭐️⭐️⭐️⭐️⭐️
1
题目描述
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。
2
题解
思路一：前缀和+二分查找
sums[i]表示数组中前i个值的和，对于每个i，我们要找到最大的下标tmp使得sums[i]-sums[tmp]>=s。因为是正整数数组，所以前缀和sums为单调增，可以使用二分查找找到合适的tmp，并且因为sums[i]-s>=sums[tmp]，所以问题等价于找到sums[i]-s在sums中的最大位置。
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
if not nums:
return 0
sums = [0]
for i in range(0,len(nums)):
sums.append(nums[i]+sums[i])
ans = len(nums)+1
for i in range(len(sums)-1,0,-1):
if sums[i]<s:
break;
target = sums[i]-s
a = 0
b = i
while a<b-1:
mid = (a+b)//2
if sums[mid]<=target:
a = mid
else:
b = mid
if mid != 0:
ans = min(ans,(i-b+1))
return 0 if ans == len(nums) + 1 else anspython中的bisect.bisect_right函数可以直接实现通过二分查找确定指定值在数组中最大位置的功能，代码得以进一步简化。
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
if not nums:
return 0
sums = [0]
for i in range(0,len(nums)):
sums.append(nums[i]+sums[i])
ans = len(nums)+1
for i in range(len(sums)-1,0,-1):
bound = bisect.bisect_right(sums,sums[i]-s)
if bound != 0:
ans = min(ans,(i-bound+1))
return 0 if ans == len(nums) + 1 else ans思路二：双指针
看官网解题的时候总能发现让我惊讶的方法，也深感自己的差距！两个指针从0开始，end指针不断往后，直至start和end间元素和>=s，此时更新长度，然后把start右移，更新长度，直至sum<s，重复end右移的过程。相当于一个变动的窗口，根据不同规则变化窗口两端，两个指针均最多移动n次（n为nums长度），且不需要额外的数组存储空间。
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
if not nums:
return 0
start = 0
end = 0
sums = 0
ans = len(nums)+1
while end < len(nums):
sums+=nums[end]
while sums>= s :
ans = min(ans,end-start+1)
sums -= nums[start]
start += 1
end += 1
return 0 if ans == len(nums) + 1 else ans本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-06-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
