Minimum Size Subarray Sum算法实现的循环终止条件问题排查

给定正整数数组nums和正整数target，返回和大于等于target的最短子数组长度；若无满足条件的子数组，返回0。

示例：

nums = [2,3,1,2,4,3]，target = 7 → 输出 = 2 
nums = [1,4,4]，target = 4 → 输出 = 1 
nums = [1,1,1,1,1,1,1,1]，target = 11 → 输出 = 0 

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

手动模拟第一个测试用例时，当j=6（等于数组长度N），还未检查[4,3]这个可能的解；另外在j=3时，疑似重复累加了nums[j]。请问代码存在什么错误？

核心错误1：循环结束后未处理剩余的有效区间 #

你的代码循环条件是j < N，当j到达数组长度时直接终止循环，但此时sumSoFar可能仍然满足>=target，却没有机会通过收缩左边界i来更新最小子数组长度。比如第一个测试用例，当j=6退出循环时，sumSoFar的值是9（包含nums[3]到nums[5]的和：2+4+3），此时还可以继续移动i，直到sumSoFar < target，过程中能得到[4,3]这个长度为2的有效解，但原代码没处理这部分逻辑。

关于“重复累加”的疑问 #

你提到的j=3时重复累加是模拟时的误解。原代码逻辑中，只有当sumSoFar < target时才会执行sumSoFar += nums[j]并让j右移，不会出现重复累加的情况。比如第一次循环到j=3时，sumSoFar是6（2+3+1），小于7，所以加上nums[3]（2）后sumSoFar变为8，j变为4，这是正常的累加逻辑，没有重复。

修正后的代码 #

在原循环结束后，添加一个额外的循环来处理剩余的sumSoFar >= target的情况：

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 += nums[j]
                j += 1
        # 处理循环结束后sumSoFar仍满足条件的情况
        while sumSoFar >= target:
            min_len = min(j - i, min_len)
            sumSoFar -= nums[i]
            i += 1
        return min_len if min_len != float('inf') else 0

这样修改后，第一个测试用例中j=6退出主循环后，会进入第二个循环：

• sumSoFar=9 >=7，更新min_len为6-3=3，sumSoFar变为7，i=4
• 再次检查sumSoFar=7 >=7，更新min_len为6-4=2，sumSoFar变为3，i=5
• 此时sumSoFar=3 <7，退出循环，最终返回2，符合预期。

内容的提问来源于stack exchange，提问作者Karina