和相等的二元子数组

-这-

给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。子数组 是数组的一段连续部分。
例如：
输入：nums = [1,0,1,0,1], goal = 2
输出：4
解释：
如下面黑体所示，有 4 个满足题目要求的子数组：
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
我写的代码：

1. class Solution(object):
   
2.     def numSubarraysWithSum(self, nums, goal):
   
3.         number = 0
   
4.         for a in range(len(nums)+1):
   
5.             for b in range(len(nums)+1):
   
6.                 if a < b:
   
7.                     text = sum(nums[a:b])
   
8.                     if text == goal:
   
9.                         number += 1
   
10.         print(number)
    
11. 
    
12. if __name__ == '__main__':
    
13.     s = Solution()
    
14.     s.numSubarraysWithSum([1,0,1,0,1],2)

复制代码

使用前缀和+哈希表方法：

1. 
   
2. from collections import Counter
   
3. class Solution:
   
4.     def numSubarraysWithSum(self,nums,goal):
   
5.         countOnes = ans = 0
   
6.         cnts = Counter({0:1})
   
7.         for num in nums:
   
8.             countOnes += num
   
9.             ans += cnts[countOnes - goal]
   
10.             cnts[countOnes] += 1
    
11.         print(ans)
    
12. 
    
13. if __name__ == '__main__':
    
14.     s = Solution()
    
15.     s.numSubarraysWithSum([1,0,1,0,1],2)

复制代码

现在就是不清楚第二个前缀和怎么遍历出来的，因为我第一个遍历结果：1、10、101、1010、10101、0、01、010、0101、1、10、101、0、01、1。那按照第二个代码的写法好像是直接相加，那这样的遍历结果是1、10、101、1010、10101.那是怎么跳到从第二个数开始遍历的呢

-这-

求助求助，基础薄弱，不明白怎么到第二数开始相加得0、01、010、0101这样

-这-

大概知道为什么可以不使用暴力破解就可以直接得到正确答案了。
第一Counter({0:1})生成一个只包含key为0，value为1的字典，后面遍历[1，0，1，0，1]。
此时countOnes += num，由于countOnes初始化值为0，开始将遍历的值相加，那么遍历5次得到的结果就是1、1、2、2、3。

1. ans += cnts[countOnes - goal]

复制代码

这行是返回字典中key对应的值，countOnes - goal 5次的结果为 ：-1、-1、0、0、1，这时由于前面两次-1key并无，所有并没有返回什么值
后面将countOnes的值作为key添加到字典中，那么后面就开始有1为key的值了。
由于后面两次2-2=0，返回两次1，并相加到 ans变量中，此时ans的值为2，
在最后一次遍历结果为3时，3-2=1，查找字典中key1的值，发现由于前面两次遍历为1，那么key1的value就是2，1+1+2就等于4了，最后返回的ans结果就是4

-这-

另外为什么3-1也可以呢，因为3是1，0，1，0，1 - 1 = 0，1，0，1或者是1，0，1，0，1 - 1，0 = 1，0，1 ，这样也是可以得到2 满足 goal = 2 的判断条件，
这就是前缀和 + 哈希表的写法，第一种我写的是暴力破解，拿索引0为开始值，结束值不断增加，第二次是索引1为开始值，结束值不断增加，这样的话 短的二元组还容易判断，如果是长度超过100的话判断的时间就是 time^2  ，如果是哈希表，那么只需要遍历一遍即可，时间就是 time 了。同时内存不会爆

-这-

真行