930. 和相同的二元子数组

# 题目

## 930. 和相同的二元子数组

[https://leetcode-cn.com/problems/binary-subarrays-with-sum/](https://leetcode-cn.com/problems/binary-subarrays-with-sum/)

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

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

**示例 1：**

```
输入：nums = [1,0,1,0,1], goal = 2
输出：4
解释：
有 4 个满足题目要求的子数组：[1,0,1]、[1,0,1,0]、[0,1,0,1]、[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`

# 题解

## 思路

前缀和+哈希。典型前缀和，这里可以利用哈希，存储出现过的次数。先用两重循环解决问题，再进一步优化。

## 代码

```javascript
/**
 * @param {number[]} nums
 * @param {number} goal
 * @return {number}
 */
// var numSubarraysWithSum = function (nums, goal) {
//     const length = nums.length;
//     // 前缀和
//     const preSum = new Array(length + 1).fill(0);
//     for (let i = 1; i <= length; i++) {
//         preSum[i] = preSum[i - 1] + nums[i - 1];
//     }
//     let ans = 0;
//     for (let i = 0; i < length; i++) {
//         for (let j = i + 1; j <= length; j++) {
//             if (preSum[j] - preSum[i] === goal) {
//                 ans++;
//             }
//         }
//     }
//     return ans;
// };

// 前缀和+哈希
var numSubarraysWithSum = function (nums, goal) {
    const length = nums.length;
    // 前缀和
    const preSum = new Array(length + 1).fill(0);
    for (let i = 1; i <= length; i++) {
        preSum[i] = preSum[i - 1] + nums[i - 1];
    }
    let ans = 0;
    const hash = new Map();
    hash.set(0, 1);
    for (let i = 1; i <= length; i++) {
        // res表示左边出现过的值，即preSum[i]-preSum[j]=goal
        let res = preSum[i] - goal;
        // 加上出现次数
        ans += hash.get(res) || 0;
        hash.set(preSum[i], (hash.get(preSum[i]) || 0) + 1);
    }
    return ans;
};
```