和相等的二元子数组
本帖最后由 -这- 于 2021-7-10 14:43 编辑给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。子数组 是数组的一段连续部分。
例如：
输入：nums = , goal = 2
输出：4
解释：
如下面黑体所示，有 4 个满足题目要求的子数组：
[1,0,1,0,1]
0,1,0,1]
1,0,1]
0,1,0,1]
我写的代码：
class Solution(object):
def numSubarraysWithSum(self, nums, goal):
number = 0
for a in range(len(nums)+1):
for b in range(len(nums)+1):
if a < b:
text = sum(nums)
if text == goal:
number += 1
print(number)
if __name__ == '__main__':
s = Solution()
s.numSubarraysWithSum(,2)
使用前缀和+哈希表方法：
from collections import Counter
class Solution:
def numSubarraysWithSum(self,nums,goal):
countOnes = ans = 0
cnts = Counter({0:1})
for num in nums:
countOnes += num
ans += cnts
cnts += 1
print(ans)
if __name__ == '__main__':
s = Solution()
s.numSubarraysWithSum(,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这样 {:10_277:}大概知道为什么可以不使用暴力破解就可以直接得到正确答案了。
第一Counter({0:1})生成一个只包含key为0，value为1的字典，后面遍历。
此时countOnes += num，由于countOnes初始化值为0，开始将遍历的值相加，那么遍历5次得到的结果就是1、1、2、2、3。
ans += cnts
这行是返回字典中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 了。同时内存不会爆 {:10_291:}真行
页:
[1]