LintCode第1712题 - 和相同的二元子数组
描述
在由若干 0 和 1 组成的数组 A 中，有多少个和为 S 的非空子数组
样例 1:
输入：A = [1,0,1,0,1], S = 2
输出：4
解释：
如下面黑体所示，有 4 个满足题目要求的子数组：
[1,0,1]
[1,0,1]
[1,0,1,0]
[0,1,0,1]样例 2:
输入：A = [0,0,0,0,0,0,1,0,0,0], S = 0
输出：27
解释：
和为 S 的子数组有 27 个思路1 采用同向双指针法 通过暴力双指针枚举所有起点 + 滑动右指针
每轮固定左指针 left，右指针从 left 向右滑动； 每次累加和，如果等于 S，就记录这个子数组； 关键点是从每个 left 出发，向右滑，不能随便跳过任何一个组合
代码1:
public class Solution {
public int numSubarraysWithSum(int[] A, int S) {
int n=A.length;
int count=0;
for(int left = 0; left < n; left++)//同向双指针法计算是否为目前值S
{
int accumulatedNum = 0;
for (int right = left; right < n; right++) {
accumulatedNum += A[right];
if (accumulatedNum == S) {
count++;
} else if (accumulatedNum > S) {
break; // 再滑动右指针没意义了
}
}
}
return count;
}
}
思路2 前缀和 + 哈希表
每轮固定左指针 left，右指针从 left 向右滑动； 每次累加和，如果等于 S，就记录这个子数组； 关键点是从每个 left 出发，向右滑，不能随便跳过任何一个组合
任意一个子数组 [i..j] 的和 = prefixSum[j] - prefixSum[i-1] 若要求 sum[i..j] = S，则等价于： prefixSum[j] - prefixSum[i-1] == S → prefixSum[i-1] == prefixSum[j] - S
prefixMap 来记录前缀和出现的次数，作用是：
| 键（Key） | 值（Value） |
|---|---|
某个前缀和 x | 这个前缀和 x 出现过多少次 |
prefixMap.put(0, 1);
前缀和为 0 出现了 1 次（这是初始化）
它允许我们从下标 0 开始的子数组也能被统计进来
accumulatedNum 当前前缀和，也就是从 A[0] 到 A[i] 的累加值
count 当前找到的子数组个数，最终返回这个值
步骤 1：累加前缀和
accumulatedNum += A[i]; // 累加前缀和 将当前元素 A[i] 累加到 accumulatedNum 中； accumulatedNum 代表前缀和 prefixSum[i]
每次比较都是当前前缀和-s 当有
既等式
prefixSum[j] - prefixSum[i-1] == S
→ prefixSum[i-1] == prefixSum[j] - S
→ accumulatedNum - S
是我们想找的值 意思为在前面的位置出现过这样一个前缀和，
这样从那个位置之后到我当前位置，就刚好是一个和为 S 的子数组
prefixMap.get(accumulatedNum - S)之前有多少个位置，它们的前缀和等于 accumulatedNum - S
每一个都可以作为「合法子数组的起点」，从那个点到当前 i 的子数组和为 S。
所以：prefixMap.get(accumulatedNum - S) 就是当前命中的合法子数组个数
prefixMap.put(accumulatedNum, prefixMap.getOrDefault(accumulatedNum, 0) + 1);
把当前的前缀和 accumulatedNum 的出现次数 +1
因为我们要统计「从前面某个位置 i 到当前位置 j 的和为 S 的子数组数量」。
每一个前缀和，都可能为后面提供组合，所以我们必须记录它出现的次数
import java.util.*;
public class Solution {
public int numSubarraysWithSum(int[] A, int S) {
int accumulatedNum = 0; // 当前的前缀和
int count = 0;
Map<Integer, Integer> prefixMap = new HashMap<>();
prefixMap.put(0, 1); // 初始化：前缀和为 0 出现了 1 次
for (int i = 0; i < A.length; i++) {
accumulatedNum += A[i]; // 累加当前前缀和
// 如果之前出现过 accumulatedNum - S，就说明找到了满足条件的子数组
if (prefixMap.containsKey(accumulatedNum - S)) {
count += prefixMap.get(accumulatedNum - S);
}
// 更新当前前缀和出现次数
prefixMap.put(accumulatedNum, prefixMap.getOrDefault(accumulatedNum, 0) + 1);
}
return count;
}
}
一个疑问点是如果不写
那么就会漏掉那些从 index = 0 开始就满足和为 S 的子数组
例 A = [1, 0, 1], S = 2
有 prefixMap.put(0, 1) 的时候：
| i | A[i] | accumulatedNum | accumulatedNum - S | prefixMap命中 | count |
|---|---|---|---|---|---|
| 0 | 1 | 1 | -1 | ❌ | 0 |
| 1 | 0 | 1 | -1 | ❌ | 0 |
| 2 | 1 | 2 | 0 | ✅ | 1 |
最终结果： 找到了子数组 [0, 1, 2]，和为 2。
当prefixMap.put(0, 1)没有的时候
当前累计为 2 的时候，你想找的前缀和是 0，但 prefixMap 里没有
prefixMap.getOrDefault(accumulatedNum, 0) 会取下标为0的值 因为没有放入1 则
这段合法子数组 [1, 0, 1] 就不会被统计 即错误结果 最终结果是:count=0
推荐刚开始学习使用双指针法 进阶使用前缀和 + 哈希表