友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
560. Subarray Sum Equals K
Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example 1:
Input: nums = [1,1,1], k = 2
Output: 2Note:
-
The length of the array is in range [1, 20,000].
-
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].
解题分析
背后的想法如下：如果累积总和（由 sum[i] 表示加到 ith 的和）最多两个指数是相同的，那么这些元素之间的元素总和为零。进一步扩展相同的想法，如果累计总和，在索引 i 和 j 处相差 k，即 sum[i]−sum[j]=k，则位于索引 i 和 j 之间的元素之和是 k。
基于这些想法，可以使用了一个哈希表 map，它用于存储所有可能的索引的累积总和以及相同累加和发生的次数。我们以以下形式存储数据：(sumi，sumi 的出现次数)。我们遍历数组 nums 并继续寻找累积总和。每当我们遇到一个新的和时，我们在 map 中创建一个与该总和相对应的新条目。如果再次出现相同的和，我们增加与 map 中的和相对应的计数。此外，对于遇到的每个总和，我们还确定已经发生 sum - k 总和的次数，因为它将确定具有总和 k 的子阵列发生到当前索引的次数。我们将 count 增加相同的量。
在完成遍历数组后，count 记录了所需结果
基于一个idea：sum[j] - sum[i] == k 的话，nums[i+1, j] 之间数字的和就是 k。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Runtime: 12 ms, faster than 97.62% of Java online submissions for Subarray Sum Equals K.
* Memory Usage: 42.2 MB, less than 5.43% of Java online submissions for Subarray Sum Equals K.
*
* Copy from: https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/he-wei-kde-zi-shu-zu-by-leetcode/[和为K的子数组 - 和为K的子数组 - 力扣（LeetCode）]
*/
public int subarraySum(int[] nums, int k) {
if (Objects.isNull(nums) || nums.length == 0) {
return 0;
}
int count = 0, sum = 0;
Map<Integer, Integer> sumToCountMap = new HashMap<>();
sumToCountMap.put(0, 1);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (sumToCountMap.containsKey(sum - k)) {
count += sumToCountMap.get(sum - k);
}
sumToCountMap.put(sum, sumToCountMap.getOrDefault(sum, 0) + 1);
}
return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* 自己根据“前缀和”套路想的思路，参考 https://leetcode.cn/problems/subarray-sum-equals-k/solutions/238572/he-wei-kde-zi-shu-zu-by-leetcode-solution/[560. 和为 K 的子数组 - 官方题解^] 更正了代码。
*/
public int subarraySum(int[] nums, int k) {
int result = 0;
if (nums == null || nums.length == 0) {
return result;
}
// key：前缀和，value：key 对应的前缀和的个数
Map<Integer, Integer> sumToCntMap = new HashMap<>();
// 对于下标为 0 的元素，前缀和为 0，个数为 1
sumToCntMap.put(0, 1);
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
// 先获得前缀和为 preSum - k 的个数，加到计数变量里
// TODO 这里为什么先检查是否存在？
if (sumToCntMap.containsKey(sum - k)) {
result += sumToCntMap.get(sum - k);
}
// 然后维护 preSumFreq 的定义
sumToCntMap.put(sum, sumToCntMap.getOrDefault(sum, 0) + 1);
}
return result;
}