LeetCode 930. 和相同的二元子数组
题目描述
题意分析
数组只包含
0和1，统计元素和恰好为goal的非空连续子数组数量。即使元素序列相同，只要左右端点不同，就算不同子数组，因此要记录满足条件的端点组合数量。
解法：前缀和 + 哈希计数
核心思路
[!blue]
定义
P[t]为前t个元素的和，且P[0]=0。右端点为r、左端点为l的区间和等于P[r+1]-P[l]；要让它等于goal，就需要此前存在P[l]=P[r+1]-goal。扫描当前元素后，用
sum表示P[r+1]，哈希表count保存此前各前缀和出现的次数。每出现一次sum-goal，就对应一个不同的合法左端点，因此把count[sum-goal]加入答案。零可能使多个前缀和相同，所以必须保存次数，不能只记录是否出现。初始先登记空前缀
0一次，对应l=0，从而覆盖从数组开头开始的区间。每轮先查询旧表，再登记当前sum，保证表中配对的前缀位置严格早于当前前缀，得到的区间一定非空；当goal=0时，这个顺序尤其不能颠倒。每个合法子数组都会在扫描到它的右端点时，由其左端点对应的前缀计入一次。不同右端点分属不同轮，同一轮又按不同左端点的次数计数，因此既不会遗漏，也不会重复统计。
解题步骤
- 初始化前缀频次 {0:1}。
- 读入元素并更新当前前缀和。
- 将此前 sum-goal 的出现次数加入答案。
- 登记当前前缀供后续位置使用。
没有出现所需前缀和时，本轮贡献为零。
goal=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(n)$，保存前缀频次。
关键点总结
[!green]
- 表中保存次数，不是单个下标或是否出现。
- 先查询再登记，排除零长度区间。
- 相同前缀和可以多次出现，每次都对应不同左端点。
易错点总结
[!yellow]
- 遗漏空前缀，会漏掉从下标零开始的区间。
- 先登记再查询，在
goal=0时会把当前前缀和自身配成空区间。- 把频次覆盖为一，会丢失对应同一前缀和的其他左端点。
- 只判断
sum是否等于goal，只能发现从开头开始的区间。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 560. 和为 K 的子数组 | 中等 | 前缀和频次法可直接处理任意整数，本题二元非负性还允许用至多目标和的窗口计数相减。 |
| 1248. 统计「优美子数组」 | 中等 | 把奇数映射成1、偶数映射成0后，原题就变成指定和的二元子数组计数。 |
| 325. 和等于 k 的最长子数组长度 | 中等 | 前缀和配合哈希表查找所需历史前缀；本题二进制数组上统计目标和，该题存最早前缀下标以最大化长度。 |
| 437. 路径总和 III | 中等 | 前缀和配合哈希表查找所需历史前缀；本题二进制数组上统计目标和，该题沿树路径维护前缀次数并回溯恢复。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！