<div>
Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum goal.
A subarray is a contiguous part of the array.
Example 1:
<pre>Input: nums = [1,0,1,0,1], goal = 2 Output: 4 Explanation: The 4 subarrays are bolded and underlined below: [<u>1,0,1</u>,0,1] [<u>1,0,1,0</u>,1] [1,<u>0,1,0,1</u>] [1,0,<u>1,0,1</u>] </pre>
Example 2:
<pre>Input: nums = [0,0,0,0,0], goal = 0 Output: 15 </pre>
Constraints:
1 <= nums.length <= 3 * 10<sup>4</sup>nums[i]is either0or1.0 <= goal <= nums.length
</div>
题目大意：
有0和1组成的字符串，求所有子数组的和等于goal的个数
解题思路Presum(推荐)：
求子数组和第一时间想到presum，然后就是presum-goal是否在hashmap中，类似于Two sum。
解题步骤：
N/A
注意事项：
- presum初始值为0，因为如果单元素数组，才能得到它的差值。
- val_to_freq的计算要在循环中，类似于Two sum，不能提前用Counter计算，否则会有重复，比如[0, 0], goal=0, 不应该为4.
Python代码：
1
2
3
4
5
6
7
8
9
10def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
presum = [0]
for i in range(len(nums)):
presum.append(presum[-1] + nums[i])
val_to_freq, res = collections.defaultdict(int), 0
for i in range(len(presum)):
if presum[i] - goal in val_to_freq:
res += val_to_freq[presum[i] - goal]
val_to_freq[presum[i]] += 1 #attn
return res
算法分析：
时间复杂度为O(n)，空间复杂度O(n)
算法II解题思路Sliding Window：
此法虽然空间复杂度较优，但较难想。求字串的和可以考虑用Two pointers两边夹。这里求所有可能性，比如0011100, goal=3, 必须包括前缀0和后缀0，所以用Two pointers最长串的模板
类似于LeetCode 340 Longest Substring with At Most K Distinct Characters，不满足条件为窗口和大于goal，所以满足条件为小于等于goal(类似于at most k)。
所以要用at_most(goal) - at_most(goal - 1)才能得到最后结果。
计算的时候，是i-left+1代表窗口和<=subgoal的以nums[i]为结尾的子数组个数，比如10101, i指向最后一个1, left指向第一个0, res是4个，对应1, 01, 101, 0101
注意事项：
- 模板满足条件在内循环外，所以计算结果在内循环结束后。
- subgoal如果小于0，返回0。比如goal为0，nums=[0,0]
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
def at_most(subgoal):
if subgoal < 0: #attn
return 0
window_sum, left, res = 0, 0, 0
i = 0
for i in range(len(nums)):
window_sum += nums[i]
while window_sum > subgoal:
window_sum -= nums[left]
left += 1
res += i - left + 1 # ending with nums[i]
return res
return at_most(goal) - at_most(goal - 1)
算法分析：
时间复杂度为O(n)，空间复杂度O(1)
