java在hashmap中存储和和和频率的直觉

ha5z0ras  于 2021-07-09  发布在  Java
关注(0)|答案(3)|浏览(369)

我们得到了一个整数数组和另一个数 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

3pmvbmvn

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 -我们的当前价值)。如果是这样,让我们增加频率计数。

z9gpfhce

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

for (int num : nums) {
        sum += num;
        count += map.getOrDefault(sum - k, 0);
        map.compute(sum, (key, value) -> (value == null) ? 1 : value + 1);
    }
piwo6bdm

piwo6bdm3#

当我们扫描 nums[] 阵列, map 会包含我们见过多少次 sum ( sum 表示从起点到当前点的数字相加)。
现在,在任何给定点,在 if ,如果我们看到 map 包含 sum-k x次,当前总和为 sum ,我们知道,我们发现了x个不同的子阵列 k . 是因为 sum 包含从起点到当前点的总和,以及 map 按从开始到某个点的和索引。如果 map 包含大于1的值,表示某个和发生多次(如果 num[] 有零或负数)。找到的子阵是从这个“确定”点到我们当前的位置,所以它必须是连续的。

相关问题