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

摘要：
前缀和+TwoSum.

题目

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

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

示例 1：

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

示例 2：

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

提示：

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

前缀和

因为要求出所有和为特定值的子数组个数，子数组是连续的，所以必然联想到前缀和。

如果预处理出前缀和数组，再暴力枚举所有子数组，复杂度为 $O(N^2)$，还是会超时。

考虑到以下标为 $i$ 的数开始，以下标为 $j$ 的数结尾的子数组的和为 $presum[j] - presum[i - 1]$，如果这个数和 $goal$ 相等，那么 $[i, j]$ 的子数组就是满足要求的。

问题就等价于求出原数组中对于每个下标 $j$，有多少小于等于 $j$ 的下标 $i$，满足:

$presum[i - 1] + goal = presum[j]$.

显然这是一个TwoSum问题。
我们可以维护一个哈希表，存放所有 $prsum[j]$ 的数量。在之后的遍历中，如果出现当前下标的前缀和减去 $goal$ 已经存在，那么 $j$ 一定和当前下标构成一个满足条件的子数组。

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        int n = nums.size();
        vector<int> presum(n + 1, 0);
        for (int i = 1; i <= n; i++) presum[i] = presum[i - 1] + nums[i - 1];
        //for (int i = 0; i < n + 1; i++) cout << presum[i] << ' ';
        //cout << endl;
        unordered_map<int, int> hash;
        hash[0]++;  // 第0项左边的虚拟的和为0，和第零项对应，如果第零项恰好等于goal，那么正好和第零项左边的和匹配
        int res = 0;
        for (int i = 1; i <= n; i++) {
            res += hash[presum[i] - goal];
            hash[presum[i]]++;
        }
        return res;
    }
};

注意每遍历到一个下标，都是先判断当前前缀和减去 $goal$ 是否已存在吗，如果存在就加上存在的数量。那么思考一下数组第 $1$ 个数的情况。

判断数组第 $1$ 个数对应前缀和减去 $goal$ 是否已存在，它对应的是未出现任何元素之前所有“元素”的和，显然 $0$ 的数量为 $1$，所以 $hash[0]$ 初始化为 $1$.

这道题和【LeetCode周赛247】C LeetCode 1915. 最美子字符串的数目非常类似。

原题链接： LeetCode 930. 和相同的二元子数组