930.和相同的二元子数组

和相同的二元子数组

给你一个二元数组 nums，和一个整数 goal，请你统计并返回有多少个和为 goal 的 非空 子数组。

子数组 是数组的一段连续部分。

示例 1:

输入：nums = [1,0,1,0,1], goal = 2
输出：4

示例 2:

输入：nums = [0,0,0,0,0], goal = 0
输出：15

提示:

• 1 <= nums.length <= 3 * 10^4
• nums[i] 不是 0 就是 1
• 0 <= goal <= nums.length

解析

使用前缀和 + 哈希表的方法，统计每个前缀和出现的次数，对于当前位置，查找前面有多少个前缀和等于当前前缀和减去 goal。

var numSubarraysWithSum = function (nums, goal) {
  const count = new Map();
  count.set(0, 1);
  let prefix = 0,
    result = 0;

  for (const num of nums) {
    prefix += num;
    result += count.get(prefix - goal) || 0;
    count.set(prefix, (count.get(prefix) || 0) + 1);
  }

  return result;
};

时间复杂度 O(n)，空间复杂度 O(n)。