在HashMap中存储和和频率的直觉 [英] Intuition behind storing sum and frequency in the HashMap

问题描述

我们得到了一个整数数组和另一个数字k，我们需要找到总和等于k的连续子数组的总数.我在LeetCode上找到了以下有趣的代码片段:

We have been given an array of integers and another number k and we need to find the total number of continuous subarrays whose sum equals to k. I found the following interesting code snippet on 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;
    }
}

我喜欢高效的解决方案，因此我试图理解它；但是我有两个问题:

I liked the efficient solution and so I am trying to understand it; however I have two questions:

1. 在HashMap中存储当前的sum及其frequency的背后直觉是什么?
2. 我们检测到的子数组连续的保证是什么?

1. What is the intuition behind storing the current sum and its frequency in the HashMap?
2. What is the guarantee that the subarray that we detect is continuous?

样本输入:[1,1,1]和k = 2;
输出:2

Sample input: [1,1,1] and k=2;
Output: 2

推荐答案

很好的算法.

让我们从一个简单的事实开始:sum(1, i) = sum(1, j) + sum(j + 1, i)(在这里我不使用Java，这是通常的数学符号) 对于任何i和j都是如此.

Lets start from simple fact: sum(1, i) = sum(1, j) + sum(j + 1, i) (I don't use Java here it is usual math notation) It is true for any i and j.

我们需要找到所有等于k的sum(j+1, i).

We need to find all sum(j+1, i) equals to k.

找到sum(1, i) = sum(1, j) + k或sum(1, i) -k = sum(1, j)

在您的程序中，sum(1, i)是sum变量.因此，我们需要检查是否有sum -k = sum(1, j)为true的任何j.希望我们在map中将所有sum(1, j)作为键.

In your program sum(1, i) is sum variable. So we need to check do we have any j for which sum -k = sum(1, j) is true. Hopefully we have all sum(1, j) as keys in our map.

我们检查map.containsKey(sum - k)，如果它是真的，那么会有这样的j给我们所需的总和.

We check map.containsKey(sum - k) and if it is true then there is such j that give us required sum.

需要使用map中的值来计算获得这种总和的多少种不同方式.

Values in map are needed to count how many different way to get such sum.

PS:顺便说一句，如果所有值都不为负，则有更好的算法.它不需要额外的内存.

PS: BTW if all values are non-negative there is better algorithm. it doesn't require extra memory.

PPS:如果您使用Java 8，我也对您的代码做了一些改进

PPS: Also I made some improvement to your code in case you in Java 8

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

这篇关于在HashMap中存储和和频率的直觉的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！