Poison

560. Subarray Sum Equals K

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0;

Map<Integer, Integer> prefixSumToCountMap = new HashMap<>();
prefixSumToCountMap.put(0, 1);

int prefixSum = 0;
for (int num : nums) {
prefixSum += num;

count += prefixSumToCountMap.getOrDefault(prefixSum - k, 0);
prefixSumToCountMap.put(prefixSum, prefixSumToCountMap.getOrDefault(prefixSum, 0) + 1);
}

return count;
}
}

注意题目输入数据中可能存在负数,可能存在重复的前缀和,所以我们引入了 HashMap 用于存储重复的前缀和个数。

Reference

560. Subarray Sum Equals K
剑指 Offer II 010. 和为 k 的子数组