带和的二元子数组的边缘情况

Question

问题
给定一个二进制数组 nums 和一个整数目标，返回具有总和目标的非空子数组的数量。

问题链接

代码

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
    

问题
当

j == N

它停止时，但它还有其他子数组需要考虑，就像你考虑

nums=[0,0,0,0]

和

goal=0

您会看到它不考虑索引 2-3 或 1-3（含）的情况。当我遇到

[0,0,0,0,0]

的情况并且我在

sumSoFar == 0

处找出我的

i=0 j=1 ([0,0] as subarray)

时，我不知道如何前进，因为如果我用 i 前进，它可能是一个子数组，如果我用 j 前进，它可能是一个子数组子数组。我必须选择一个，因此我错过了其他可能的子数组，并且我的计数低于应有的数量。

Answer 1

您已经正确地识别了问题：您通过增加两个索引之一并且永远不会使用相同的索引返回而错过了可能性。

分析

查看示例然后发现有用的逻辑可能会有所帮助。假设输入是 [0,0,0,0,1,0,1,0,0,1,0]，目标是 2。那么我们将拥有包含前两个 1 的子列表，或后两个 1。对于每一个，我们都可以选择在其左侧和/或右侧包含一些零。我们可以想象如下：

[0,0,0,0,1,0,1,0,0,1,0]
 <<<<<<<<----->>>>
           <<------->>

中间线中的破折号表示前两个 1 的所有列表的一部分，“箭头”表示我们可以灵活地将列表向左或向右“增长”（抓取内部的零）列表）。

那么问题是：这些列表有多少个？

如果我们查看第一组列表（具有前两个 1），对于这样的列表，我们有 5 个可能的 starting 点和 3 个可能的 ending 点。所以我们可以得出这样的列表有 5*3=15 个。如果我们将相同的原则应用于最后两个 1 的列表，则该乘积为 2*2=4。

因此，获取 1 秒左右的距离或“间隙”将很有用。对于示例输入，我们可以得出有 5 种方法可以在第一个 1 之前开始一个列表，即那里的 0 数量加 1。然后我们有 2 种方法在第二个 1 之前开始一个列表，...等等。这为我们提供了这个特定输入的 [5, 2, 3, 2] 的“间隙”列表。有了这个，我们就拥有了有关输入的所有信息，并且算法的其余部分只能以此为基础。请记住，我们想要将 5*3 和 2*2 相乘：这些条目在此“间隙”列表中相隔 2 个槽，换句话说，它们相隔

goal

个槽！

有了这些信息，我们可以在这个派生列表上滑动一个宽度为

goal

的窗口，并获得我们需要的所有产品。

当

goal

为零时存在边缘情况。在这种情况下，我们不需要两个不同“间隙”的乘积，而是计算可以由单段零组成多少个列表。这确实是一个三角数，所以我们可以使用公式 𝑛(𝑛−1)/2。

实施

有了上述见解，我们就可以实施解决方案了。

我在这里提供一个剧透解决方案：

    def numSubarraysWithSum(self, nums, goal):
         # Create a gap-list, i.e. a list of distances between two 1s
         gaps = []
         j = 0
         for i, value in enumerate(nums):
             if value:
                 gaps.append(i - j + 1)
                 j = i + 1
         gaps.append(len(nums) - j + 1)

         if goal == 0:  # Edge case: sum up triangular numbers
             return sum(gap * (gap - 1) // 2 for gap in gaps)
         else:
             return sum(before * after for before, after in zip(gaps, gaps[goal:]))