题目描述:
题解:
题解一(超时):
1.numsum保存nums数组的前缀和,即numsum[i]=nums[0]+nums[1]+...+nums[i]
2.nums[i]+num[i+1]+...+nums[j]可以转化为numsum[j]-numsum[i]
3.对numsum进行遍历,找到满足numsum[j]-numsum[i]>=target的最小的j-i。
class Solution(object): def minSubArrayLen(self, target, nums): n = len(nums) numsum = [0]*n numsum[0] = nums[0] for i in range(1,n): numsum[i] = numsum[i-1]+nums[i] minlen = n for i in range(n): if numsum[i]>=target: if minlen>i+1: minlen = i+1 for j in range(i,n): if numsum[j]-numsum[i]>=target: if minlen>(j-i): minlen = j-i if numsum[n-1]<target: return 0 return minlen
题解二(通过):
参考:209 长度最小的子数组(前缀和+二分查找、滑动窗口)_二哈-CSDN博客
1.numsum表示数组nums的前缀和,不同的是numsum[i]=0,i>=1时,numsum[i]=nums[0]+...+nums[i-1]
2.minlen初始化为n+1
3.对numsum[i],构造mytarget=target+numsum[i],通过调用python内置函数bisect.bisect_left(numsum,target)确定将mytarget插入numsum的位置bound(如果mytarget已经存在于numsum,则返回该位置左边的位置序号)。
4.如果bound = len(numsum),即mytarget只能插入numsum最后一个位置,说明numsum中不存在numsum[j]>=numsum[i]+target,即不存在一段和大于target的连续数组。
5.更新minlen。
其中将numsum[0]设为0,是考虑到连续数组可能从num[0]开始的情况。
class Solution: def minSubArrayLen(self, target,nums): if not nums: return 0 n = len(nums) numsum = [0] for i in range(n): numsum.append(numsum[-1]+nums[i]) minlen = n+1 for i in range(0,n): mytarget = target+numsum[i] bound = bisect.bisect_left(numsum,mytarget) if bound!=len(numsum): minlen = min(minlen,bound-i) return 0 if minlen==n+1 else minlen