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

示例 1：

  1. 输入：nums = [1,0,1,0,1], goal = 2
  2. 输出：4
  3. 解释：
  4. 如下面黑体所示，有 4 个满足题目要求的子数组：
  5. [1,0,1,0,1]
  6. [1,0,1,0,1]
  7. [1,0,1,0,1]
  8. [1,0,1,0,1]

示例 2：

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


提示：

  • 1 <= nums.length <= 3 * 104
  • nums[i] 不是 0 就是 1

  • 0 <= goal <= nums.length

    解法一：递归（内存超了）

    func numSubarraysWithSum(nums []int, goal int) int {
  var res, start int
  var recursion func(target, idx int)
  recursion = func(target, idx int) {
      if start >= len(nums) {
          return
      }
      if idx >= len(nums) {
          start++
          recursion(goal, start)
          return
      }
      if target == nums[idx] {
          res++
          recursion(target-nums[idx], idx+1)
      } else if target > nums[idx] {
          recursion(target-nums[idx], idx+1)
      } else if target < nums[idx] {
          start++
          recursion(goal, start)
      }
  }
  recursion(goal, start)
  return res
}

    解法二：前缀和 + 哈希表

    这么写可能好理解点。
    假设 [i, j) 正好满足 goal， 那么就有 sum[j] - sum[i] = goal
    所以这个问题就转换成我们求有多少个 sum[j] - goal 满足的 sum[i] 即可

    func numSubarraysWithSum(nums []int, goal int) int {
  var res, sum int
  // key 开头到当前位置的和  value 等于这个和的有几个值

  var hash = map[int][]int{}
  for key, num := range nums {
      hash[sum] = append(hash[sum], key)
      sum += num
      res += len(hash[sum-goal])
  }
  return res
}

    上面的 slice 也是没用的，可以直接用 int 计数即可

    func numSubarraysWithSum(nums []int, goal int) int {
  var res, sum int
  var hash = map[int]int{}
  for _, num := range nums {
      hash[sum] ++
      sum += num
      res += hash[sum-goal]
  }
  return res
}