LeetCode二进制数组目标和子数组计数代码错误排查

问题 #

给定二进制数组nums和整数goal，返回和为goal的非空子数组数量。

问题代码 #

class Solution:
    def numSubarraysWithSum(self, nums, goal):
        count,i,j,sumSoFar=0,0,0,0
        N=len(nums)
        while j < N:
            if sumSoFar==goal:
                print('my solution is [' , i , j , ']')
                count+=1
                sumSoFar+=nums[j]
                j+=1
            elif sumSoFar > goal:
                sumSoFar-=nums[i]
                i+=1
            else:
                sumSoFar+=nums[j]
                j+=1
        while i < N:
            if sumSoFar == goal:
                count+=1
            sumSoFar-=nums[i]
            i+=1
        return count

solution = Solution()
array = [1,0,1,0,1]
goal = 2
a = solution.numSubarraysWithSum(array,goal) #expected 4
print(a) # Output: 4

array = [0,0,0,0,0]
goal = 0
a = solution.numSubarraysWithSum(array,goal) #expected 15
print(a) # Output: 10

代码缺陷说明 #

当前代码存在逻辑漏洞：处理全0数组时会遗漏大量符合条件的子数组。比如输入nums=[0,0,0,0,0]、goal=0时，预期结果为15，但实际输出仅为10。原因是当sumSoFar等于goal时，代码仅移动右指针j，完全没考虑移动左指针i能得到的有效子数组，导致大量符合要求的子数组未被统计。

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