Problem

给定一个由正整数nums和正整数target组成的数组,返回其子数组的最小长度 总和大于或等于目标.如果没有这样的子数组,则返回0.

问题链接:209. Minimum size subarray sum

下面是一些示例:

nums = [2,3,1,2,4,3] target = 7 output = 2 
nums = [1,4,4] target = 4 output = 1 
nums = [1,1,1,1,1,1,1,1] target = 11 output = 0 

My thought process

class Solution(object):
    def minSubArrayLen(self, target, nums):
        i,j,sumSoFar=0,0,0
        N = len(nums)
        if N == 0:
            return 0
        min_len=float('inf')
        while j < N:
            if sumSoFar >= target:
                min_len = min(j-i, min_len)
                sumSoFar-=nums[i]
                i+=1
            else: #sumSoFar is less than target
                sumSoFar+=nums[j]
                j+=1
        if min_len == float('inf'):
            return 0
        return min_len

Issue

当在第一种情况(nums = [2,3,1,2,4,3],target = 7)中try 手工解决时, 我到了j=6,然后才能把[3,4]作为可能的解决方案,因为j == N/6.还有,我觉得 当我达到if的条件时,我加两次nums[j](在j=3).

我做错了什么?

推荐答案

您的 idea 很好,但是当j达到N时,循环将结束,这会阻止您在Nums的末尾找到合法的子array.在循环条件上加上or sumSoFar >= target将允许算法在该情况下继续.

以下是一个可行的解决方案:

from math import inf

class Solution(object):
    def minSubArrayLen(self, target, nums):
        i=0
        j=0
        min_len = inf
        sumSoFar=0

        while j < len(nums) or sumSoFar >= target:
            if sumSoFar >= target:
                min_len = min(min_len, j - i)
                sumSoFar -= nums[i]
                i += 1
            else:  # sumSoFar is less than target
                sumSoFar += nums[j]
                j += 1
        return min_len if min_len != inf else 0

例如: Solution().minSubArrayLen(7, [2, 3, 1, 2, 4, 3]) # 2

Python相关问答推荐

三个给定的坐标可以是矩形的点吗

Python上的Instagram API:缺少client_id参数"

通过Selenium从页面获取所有H2元素

从dict的列中分钟

部分视图的DataFrame

Maya Python脚本将纹理应用于所有对象,而不是选定对象

matplotlib图中的复杂箭头形状

在输入行运行时停止代码

为什么调用函数的值和次数不同,递归在代码中是如何工作的?

Pandas—堆栈多索引头,但不包括第一列

Python类型提示:对于一个可以迭代的变量,我应该使用什么?

Pandas 数据帧中的枚举,不能在枚举列上执行GROUP BY吗?

应用指定的规则构建数组

Scipy差分进化:如何传递矩阵作为参数进行优化?

从列表中分离数据的最佳方式

在任何要保留的字段中添加引号的文件,就像在Pandas 中一样

Groupby并在组内比较单独行上的两个时间戳

根据边界点的属性将图划分为子图

Sknowled线性回归()不需要迭代和学习率作为参数

如何使用count()获取特定日期之间的项目