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

2021-12-07 HGNULB 约 9 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

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

题意分析

给一个只含 0 和 1 的数组 nums 和一个非负整数 goal，统计有多少个非空连续子数组的元素和恰好等于 goal。

「连续子数组」是关键词——不是子序列，所以每个候选都由一对下标 (左端, 右端) 唯一确定，共 $O(n^2)$ 个候选。题目要的是个数而不是具体位置，这意味着不需要枚举出每一个，只要能数对就行。

数组只含 0 和 1 这一点，让前缀和具有单调不减的性质，从而衍生出滑动窗口做法；但它并不是必需条件——本题的主流解法对任意非负数组都成立。

goal 可以为 0，这是最容易被忽略的边界：此时要统计的是「全是 0 的连续段」的子数组个数，一段长度为 m 的连续 0 会贡献 $\frac{m(m+1)}{2}$ 个。任何依赖「窗口内至少有一个 1」的实现都会在这里翻车。

约束里 $n$ 最大 3 万，$O(n^2)$ 的暴力枚举是 9 亿次，超时；需要 $O(n)$ 或 $O(n \log n)$。

边界：goal 大于数组中 1 的总数时答案是 0；数组全是 1、goal = 0 时答案也是 0；单元素数组时直接判断该元素是否等于 goal。

解法：前缀和 + 哈希计数

核心思路

暴力做法是枚举左右端点、累加区间和，$O(n^2)$（配合前缀和数组）或 $O(n^3)$（每次重新求和）。$n = 3$ 万时都不可接受。

瓶颈在于我们对每个右端点，都要把所有左端点重新试一遍。但换个写法就能看出浪费在哪：记 $P_i$ 为前 i 个元素的和（$P_0 = 0$），则子数组 nums[l..r] 的和等于 $P_{r+1} - P_l$。要求这个差等于 goal，即
\[P_l = P_{r+1} - goal\]
也就是说，固定右端点后，合法左端点的个数 = 在它之前出现过多少个值为 $P_{r+1} - goal$ 的前缀和。这不再需要枚举，只需要「查一个数出现过几次」——哈希表的本职工作。

于是算法变成一趟扫描：维护当前前缀和 sum 和一张「前缀和值 → 出现次数」的哈希表 count。每读入一个元素就更新 sum，先累加 count[sum - goal] 到答案，再把当前的 sum 记进表里。

不变量：处理完第 i 个元素后，count 中记录的恰好是 $P_0, P_1, \dots, P_i$ 这 i+1 个前缀和各自的出现次数，而 answer 恰好等于「右端点落在前 i 个元素之内的、和为 goal 的子数组总数」。

两个顺序细节决定成败。

第一，count[0] = 1 必须预先放入。它代表空前缀 $P_0 = 0$，对应「子数组从下标 0 开始」的情形。没有它，nums = [1]、goal = 1 会算出 0 而不是 1。

第二，先查询再写入。若先把当前 sum 计数再去查 count[sum - goal]，当 goal = 0 时 sum - goal == sum，刚写进去的自己会被查到，等于把长度为 0 的空子数组算进答案，每个位置都多算一次。查询在前，天然保证配对的左端点严格在当前位置之前。

顺带说明为什么不必特意为 goal = 0 写分支：此时查询的是 count[sum]，也就是「之前有多少个前缀和与当前相同」，而两个相同的前缀和之间夹的正是一段和为 0 的区间——公式自动覆盖了「连续 0 段」的组合计数，不需要额外的 $\frac{m(m+1)}{2}$ 公式。

解题步骤

初始化 count = {0: 1}、sum = 0、answer = 0：那个 {0: 1} 是空前缀的席位，它让「从下标 0 开始的子数组」也能被正常配对。漏掉它会让所有以数组开头为左端点的答案全部丢失。

遍历数组，先更新 sum += x：sum 始终表示「包含当前元素在内」的前缀和，也就是 $P_{r+1}$。

再累加 answer += count.getOrDefault(sum - goal, 0)：这一行回答的是「有多少个更早的前缀和等于 sum - goal」，每一个都对应一个以当前位置结尾的合法子数组。查不到时按 0 计，不能抛异常也不能跳过。

最后 count[sum]++：把当前前缀和登记进表，供后续位置查询。这三步的顺序（更新和 → 查询 → 登记）不能调换，尤其登记必须排在查询之后。

返回 answer：不需要任何后处理，也不需要减去空子数组——先查后写已经排除了它。

以 nums = [1,0,1,0,1]、goal = 2 走一遍，正确答案是 4。

初始：count = {0:1}，sum = 0，answer = 0。

读入 nums[0] = 1：sum = 1。查 count[1 - 2] = count[-1]，不存在，加 0，answer = 0。登记 count[1] = 1。表：{0:1, 1:1}。

读入 nums[1] = 0：sum = 1。查 count[-1]，仍不存在，answer = 0。登记后 count[1] = 2。表：{0:1, 1:2}。这里 count[1] 变成 2，记录的是「前缀和为 1」出现过两次（前 1 个元素、前 2 个元素），后面会派上用场。

读入 nums[2] = 1：sum = 2。查 count[2 - 2] = count[0] = 1，answer = 1。这一个对应子数组 nums[0..2] = [1,0,1]，和为 2。登记 count[2] = 1。表：{0:1, 1:2, 2:1}。

读入 nums[3] = 0：sum = 2。查 count[0] = 1，answer = 2。新增的是 nums[0..3] = [1,0,1,0]，和仍为 2。登记后 count[2] = 2。

读入 nums[4] = 1：sum = 3。查 count[3 - 2] = count[1] = 2，answer = 4。一次加了 2，对应两个子数组：nums[1..4] = [0,1,0,1] 和 nums[2..4] = [1,0,1]——它们的左端点分别是「前缀和为 1」的两个位置。登记 count[3] = 1。

返回 4。手工核对：和为 2 的子数组是 [1,0,1]（下标 0-2）、[1,0,1,0]（0-3）、[0,1,0,1]（1-4）、[1,0,1]（2-4），恰好 4 个，一致。

再验证一下 count[0] = 1 的必要性：如果初始表为空，第三步查 count[0] 会得到 0，nums[0..2] 这个答案就漏了，最终返回 2 而不是 4。

以及「先查后写」的必要性：把 nums = [0,0]、goal = 0 代进去，正确答案是 3（[0]、[0]、[0,0]）。按正确顺序：第一步 sum = 0，查 count[0] = 1，answer = 1，登记后 count[0] = 2；第二步 sum = 0，查 count[0] = 2，answer = 3，正确。若先登记再查询，第一步会查到刚写入的自己，answer 变成 2，第二步再多算一次变成 5，凭空多出两个长度为 0 的「空子数组」。

代码实现

class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        Map<Integer, Integer> count = new HashMap<>();
        count.put(0, 1);

        int sum = 0;
        int answer = 0;
        for (int x : nums) {
            sum += x;
            answer += count.getOrDefault(sum - goal, 0);
            count.put(sum, count.getOrDefault(sum, 0) + 1);
        }
        return answer;
    }
}

func numSubarraysWithSum(nums []int, goal int) int {
    count := map[int]int{0: 1}
    sum := 0
    answer := 0

    for _, x := range nums {
        sum += x
        answer += count[sum-goal]
        count[sum]++
    }
    return answer
}

复杂度分析

时间复杂度：$O(n)$。数组只扫一遍，每个位置做常数次哈希查询与写入（均摊 $O(1)$），没有任何回退或嵌套。

空间复杂度：$O(n)$。哈希表最多存下 $n + 1$ 个不同的前缀和值。由于本题元素非负、前缀和取值范围是 $0$ 到 $n$，也可以把哈希表换成长度 $n+1$ 的数组，常数更小但阶数不变。

关键点总结

「连续子数组的和等于定值」的标准范式就是前缀和加哈希：把区间和条件 $P_r - P_l = goal$ 改写成 $P_l = P_r - goal$，于是「枚举左端点」变成「查一个数出现过几次」。

count[0] = 1 是空前缀的席位，它让「从下标 0 开始」的子数组能被正常配对。这个初始化不是可选的细节，而是整套推导的一部分。

「先查询后登记」保证了配对的左端点严格早于当前位置，同时自动排除空子数组。goal = 0 就是检验这个顺序的试金石。

求的是个数而非某个具体子数组，所以哈希表存的是「出现次数」而不是「下标」；存下标只能回答存在性或最值类问题。

goal = 0 不需要单独分支：相同前缀和之间夹的正是和为 0 的区间，组合计数被公式自然覆盖。

面试视角：先说暴力 $O(n^2)$，再点出「固定右端点后左端点的条件是一个等式」，最后落到哈希计数——这条推导链适用于 560、974、1248 一整类题，讲清楚一次就能复用。

易错点总结

漏掉 count[0] = 1：nums = [1]、goal = 1 会返回 0，正确答案是 1；所有以数组开头为左端点的子数组全部丢失。

先登记 count[sum]++ 再查询：nums = [0,0]、goal = 0 会返回 5，正确答案是 3——空子数组被重复计入。

查询写成 count[goal - sum]：把等式方向搞反，nums = [1,0,1]、goal = 2 会返回 0 而不是 1。正确的是 count[sum - goal]。

查不到时不按 0 处理：Java 里直接 count.get(sum - goal) 会返回 null 并在自动拆箱时空指针；必须用 getOrDefault。

用数组代替哈希表却不做负下标保护：sum - goal 在 goal 较大时为负，arr[-1] 直接越界；换数组实现时必须显式判 sum >= goal。

误以为可以用「和不超过 goal 的窗口数」直接相减而漏掉边界：atMost(goal) - atMost(goal - 1) 的写法在 goal = 0 时会调用 atMost(-1)，若该函数不返回 0 就会算出负数。

用滑动窗口但收缩条件写成 sum > goal：goal = 0、nums = [0,0,0] 时窗口永远不收缩，且「恰好等于」需要同时统计左边界的多种取法，单纯的双指针会漏算重复 0 的组合。

把子数组当成子序列：nums = [1,0,1]、goal = 2 若允许不连续会数出更多方案，正确答案只统计连续区间。

答案变量用 int 却担心溢出而改成取模：$n = 3$ 万时最坏答案约 $4.5 \times 10^8$，仍在 int 范围内，题目也未要求取模，擅自取模会答错。

在循环外统一登记所有前缀和再统计：这样每个右端点会把它之后的前缀和也算进来，nums = [1,1]、goal = 1 会返回 4 而不是 2。

返回子数组列表而不是数量：题目问的是个数，构造出所有子数组既没必要也会退化到 $O(n^2)$。

相似题目

题目	难度	考察点
560. 和为 K 的子数组	中等	与本题同一套模板，但元素可为负，因此滑动窗口不成立，只能用哈希计数
974. 和可被 K 整除的子数组	中等	哈希键换成前缀和的模，负数取模要先加 K 再取模
1248. 统计「优美子数组」	中等	把奇数记为 1、偶数记为 0，就完全退化成本题
523. 连续的子数组和	中等	存的是模值的最早下标而非次数，因为要判长度至少为 2 的存在性
525. 连续数组	中等	把 0 记为 -1 后求「和为 0 的最长子数组」，哈希存最早下标以求最长
992. K 个不同整数的子数组	困难	用「恰好 K = 至多 K − 至多 K−1」的差分技巧，是本题的滑窗解法的推广
713. 乘积小于 K 的子数组	中等	条件是「小于」而非「等于」，元素全为正时可直接滑动窗口累加窗口长度
209. 长度最小的子数组	中等	求最短长度而非个数，正数前提下用双指针单调收缩即可
LCR 010. 和为 K 的子数组	中等	与 560 同题