Leetcode560. 和为 K 的子数组
Leetcode560. 和为 K 的子数组
题目：
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
题解：
前缀和 + 哈希表
我们定义
pre
[
i
]
\textit{pre}[i]
pre[i] 为
[
0..
i
]
[0..i]
[0..i] 里所有数的和，则
pre
[
i
]
\textit{pre}[i]
pre[i] 可以由
pre
[
i
−
1
]
\textit{pre}[i-1]
pre[i−1] 递推而来，即：
pre [ i ] = pre [ i − 1 ] + nums [ i ] \textit{pre}[i]=\textit{pre}[i-1]+\textit{nums}[i] pre[i]=pre[i−1]+nums[i]
那么【 [ j . . i ] [j..i] [j..i] 这个子数组和为 k k k 】这个条件我们可以转化为
pre [ i ] − pre [ j − 1 ] = = k \textit{pre}[i]-\textit{pre}[j-1]==k pre[i]−pre[j−1]==k
简单移项可得符合条件的下标 j j j 需要满足
pre [ j − 1 ] = = pre [ i ] − k \textit{pre}[j-1] == \textit{pre}[i] - k pre[j−1]==pre[i]−k
所以我们考虑以 i i i 结尾的和为 k k k 的连续子数组个数时只要统计有多少个前缀和为 pre [ i ] − k \textit{pre}[i]-k pre[i]−k的 pre [ j ] \textit{pre}[j] pre[j] 即可。我们建立哈希表 mp \textit{mp} mp，以和为键，出现次数为对应的 pre [ j ] \textit{pre}[j] pre[j]的下标范围是 0 ≤ j ≤ i 0\leq j\leq i 0≤j≤i 。同时，由于 pre [ i ] \textit{pre}[i] pre[i]的计算只与前一项的答案有关，因此我们可以不用建立 pre \textit{pre} pre 数组，直接用 pre \textit{pre} pre 变量来记录 p r e [ i − 1 ] pre[i-1] pre[i−1] 的答案即可。
java代码：
/**
* @param nums
* @param k
* @return
*/
public static int subarraySum(int[] nums, int k) {
int count = 0, pre = 0;
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
for (int i = 0; i < nums.length; i++) {
pre += nums[i];
if (map.containsKey(pre - k)) {
count += map.get(pre - k);
}
map.put(pre, map.getOrDefault(pre, 0) + 1);
}
return count;
}