[leetcode] 930. Binary Subarrays With Sum

[leetcode] 930. Binary Subarrays With Sum

Description

In an array A of 0s and 1s, how many non-empty subarrays have sum S?

Example 1:

Input: A = [1,0,1,0,1], S = 2Output: 4Explanation: The 4 subarrays are bolded below:[1,0,1,0,1][1,0,1,0,1][1,0,1,0,1][1,0,1,0,1]

Note:

A.length <= 300000 <= S <= A.lengthA[i] is either 0 or 1.

分析

题目的意思是：给定一个数组，求出和为给定S的子数组。这道题我参考了一下答案的思路，用preSum的方法：

首先用preSum对数组的每个位置进行求和，另preSum=A[0] + A[1] + … + A[i-1] ，Then preSum[j+1] - preSum[i] = A[i] + A[i+1] + … + A[j], 是数组 [i, j]区间的和.然后我们记录 preSum[j] = preSum[i] + S的个数就是最终的答案了哈,这等价于求以j结尾且和为S的个数了。

比如：A = [1,0,1,0,1], S = 2

defaultdict(, {0: 0, 2: 1, 1: 0, 3: 2, 4: 2, 5: 1}) 其中key是preSum的值，value为频率

有点不太好理解，需要手动算一下啦 我开始用双指针的做法没办法解决为0的情况。

代码

class Solution: def numSubarraysWithSum(self, A: List[int], S: int) -> int: res=0 preSum=[0] for x in A: preSum.append(preSum[-1]+x) d=defaultdict(int) for x in preSum: res+=d[x] d[x+S]+=1 return res

参考文献

​​Approach 2: Prefix Sums​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。