leetcode 209. 长度最小的子数组 python

题目描述:

leetcode 209. 长度最小的子数组 python  

题解:

 题解一(超时):

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

leetcode 209. 长度最小的子数组 python

 

 

 

 

上一篇:209. 长度最小的子数组


下一篇:【AI视野·今日CV 计算机视觉论文速览 第209期】Mon, 31 May 2021