我们得到了一个整数数组和另一个数 k
我们需要求出连续子阵的总数,其和等于 k
. 我在leetcode上发现了以下有趣的代码片段:
public class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0, sum = 0;
HashMap < Integer, Integer > map = new HashMap < > ();
map.put(0, 1);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (map.containsKey(sum - k))
count += map.get(sum - k);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
}
我喜欢有效的解决方案,所以我试图理解它;不过,我有两个问题:
储存电流背后的直觉是什么 sum
以及它的 frequency
在hashmap中?
我们检测到的子阵列是连续的,有什么保证?
样本输入: [1,1,1]
和k= 2
;
输出: 2
3条答案
按热度按时间3pmvbmvn1#
3个关键点:
第一个键是0
增加
count
只有当一把钥匙sum - k
已经在Map上了把每个和与它的频率对应起来
我将其分为三种情况:
第一:大于零的数字。
每个键的频率等于1。
那么计数是如何增加的呢?它只能在键已经在Map中时增加。钥匙都是以前的总和。所以当前的条件键
if (map.containsKey(sum - k))
是sum - k
. 如果sum - k
是一个键,意思是在上一个和之间(sum - k
)当前和是和相等的元素k
(原因)k + (sum - k) = sum
-我们的当前价值)。所以我们可以增加count
-我们找到了子数组。第二:大于或等于零的数字。
所以现在我们可以把零放在中间。差别不大,但你可以想象如果我们增加
count
在下一步中,我们的nums
数组。在这种情况下,我们将增加
count
又正常了。包括零,我们的频率会改变。想象一下这个例子:
subarraySum({0, 0, 0, 7, 0}, 7);
结果是8。记住第一个键是0。所以当我们迭代到7时,我们得到了一个Map(0: 4)
. 现在sum = 7
以及7 - 7 = 0
所以,我们有3个,所以这个时间计数增加了这个频率。现在我们从数组-0中选取最后一个元素。此键的值仍然是4。sum - k
还是一样,所以我们的count
增加4。第三:整数。
我想你明白了;)这一次负数可能也会增加一些频率。如果我们有钥匙
sum - key
在一张Map上,它意味着(sum - k
)现在我们有了整数,求和为k
(原因)k + (sum - k) = sum
-我们的当前价值)。如果是这样,让我们增加频率计数。z9gpfhce2#
不错的算法。
让我们从简单的事实开始:
sum(1, i) = sum(1, j) + sum(j + 1, i)
(我这里不使用java,这是常用的数学表示法)这对任何人都是正确的i
以及j
.我们需要找到所有的
sum(j+1, i)
等于k
.这是相同的发现
sum(1, i) = sum(1, j) + k
或者sum(1, i) -k = sum(1, j)
在你的程序中sum(1, i)
是sum
变量。所以我们需要检查一下有没有j
为了什么sum -k = sum(1, j)
这是真的。希望我们都有sum(1, j)
作为我们的钥匙map
.我们检查一下
map.containsKey(sum - k)
如果这是真的,那么就有这样的问题j
给了我们所需的金额。需要map中的值来计算有多少种不同的方法可以得到这样的和。
顺便说一句,如果所有的值都是非负的,有更好的算法。它不需要额外的内存。
pps:我还对您的代码做了一些改进,以防您使用java8
piwo6bdm3#
当我们扫描
nums[]
阵列,map
会包含我们见过多少次sum
(sum
表示从起点到当前点的数字相加)。现在,在任何给定点,在
if
,如果我们看到map
包含sum-k
x次,当前总和为sum
,我们知道,我们发现了x个不同的子阵列k
. 是因为sum
包含从起点到当前点的总和,以及map
按从开始到某个点的和索引。如果map
包含大于1的值,表示某个和发生多次(如果num[]
有零或负数)。找到的子阵是从这个“确定”点到我们当前的位置,所以它必须是连续的。