查找总和等于k的子数组的数量 [英] Finding number of subarrays whose sum equals `k`

问题描述

我们将得到一个整数数组和一个值 k 。我们需要找到总和等于 k 的子数组总数。

We would be given an array of integers and a value k. We need to find the total number of sub-arrays whose sum equals k.

我在Leetcode上在线找到了一些有趣的代码，如下所示：

I found some interesting code online (on Leetcode) which is as follows:

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int sum = 0, result = 0;
        Map<Integer, Integer> preSum = new HashMap<>();
        preSum.put(0, 1);

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (preSum.containsKey(sum - k)) {
                result += preSum.get(sum - k);
            }
            preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
        }

        return result;
    }
}

要了解它，我介绍了一些具体示例，例如 [1,1,1,1,1] ，其中 k = 3 和 [1 ，2,3,0,3,2,6] ，其中 k = 6 。尽管代码在两种情况下均能完美运行，但我无法遵循其实际计算输出的方式。

To understand it, I walked through some specific examples like [1,1,1,1,1] with k=3 and [1,2,3,0,3,2,6] with k=6. While the code works perfectly in both the cases, I fail to follow how it actually computes the output.

1）为什么代码在不将其归零的情况下连续添加数组中的值？例如，如果 [1,1,1,1,1] 且 k = 3 ，则一次 sum = 3 ，我们是否不需要将 sum 重置为零？

1) Why does the code continuously add the values in the array, without ever zeroing it out? For example, in case of [1,1,1,1,1] with k=3, once sum=3, don't we need to reset sum to zero? Doesn't not resetting sum interfere with finding later subarrays?

2）难道不重置 sum 会干扰以后的子数组吗？2）我们不应该简单地执行结果++ ，当我们找到总和为 k 的子数组时？为什么我们改为添加 preSum.get（sum-k）？

2) Shouldn't we simply do result++ when we find a subarray of sum k? Why do we add preSum.get(sum-k) instead?

推荐答案

< h2>让我们首先处理您的第一个困惑点：

代码不断对数组求和并且不重置 sum 是因为我们在进行时将总和保存在 preSum （以前的总和）中。然后，只要我们到达 sum-k 是先前的总和（例如，索引 i ），我们知道 索引 i 与当前索引之间的总和就是 k 。

Let's handle your first point of confusion first:

The reason the code keeps summing the array and doesn't reset sum is because we are saving the sum in preSum (previous sums) as we go. Then, any time we get to a point where sum-k is a previous sum (say at index i), we know that the sum between index i and our current index is exactly k.

例如，在下面的图像中， i = 2 ，而我们当前的索引等于 4 ，我们可以看到从 9 开始，当前索引的总和减去 3 ，索引 i 的总和为 6 ，索引 2之间的总和和 4 （含）是 6 。

For example, in the image below with i=2, and our current index equal to 4, we can see that since 9, the sum at our current index, minus 3, the sum at index i, is 6, the sum between indexes 2 and 4 (inclusive) is 6.

对此进行思考的另一种方法是看到丢弃 [1,2 ] 的数组（在当前索引为 4 的情况下）为子数组，总和为 6 ，原因与上述类似（详情请参见图片）。

Another way to think about this is to see that discarding [1,2] from the array (at our current index of 4) gives us a subarray of sum 6, for similar reasons as above (see image for details).

使用我我们可以说，我们想从数组的前面丢弃，直到剩下总和为 k 的子数组。我们可以这样说：对于每个索引，只丢弃 1 ，然后丢弃 1 + 2 ，然后丢弃 1 + 2 + 3 等（这些数字来自我们的示例），直到找到总和为 k 的子数组（在我们的示例中， k = 6 ）。

Using this method of thinking, we can say we want to discard from the front of the array until we are left with a subarray of sum k. We could do this by saying, for each index, "discard just 1, then discard 1+2, then discard 1+2+3, etc" (these numbers are from our example) until we found a subarray of sum k (k=6 in our example).

这给出了一个非常有效的解决方案，但请注意，我们会这样做这在我们数组的每个索引处，因此一遍又一遍地求和相同的数字。一种节省计算的方法是保存这些和以供以后使用。更好的是，我们已经将这些相同的数字求和以获得当前的 sum ，因此我们可以随便保存该总数。

That gives a perfectly valid solution, but notice we would be doing this at every index of our array, and thus summing the same numbers over and over. A way to save computation would be to save these sums for later use. Even better, we already sum these same numbers to get our current sum, so we can just save that total as we go.

要找到一个子数组，我们可以查看保存的总和，减去它们，然后测试剩下的是 k 。必须减去每个保存的总和，这有点烦人，因此我们可以使用减法的可交换性看看如果 sum-x = k 为真，则 sum-k = x 也为真。这样，我们就可以看到 x 是否是保存的总和，如果是，就知道我们找到了大小为 k 。哈希图使此查找有效。

To find a subarray, we can just look through our saved sums, subtracting them and testing if what we are left with is k. It is a bit annoying to have to subtract every saved sum, so we can use the commutativity of subtraction to see that if sum-x=k is true, sum-k=x is also true. This way we can just see if x is a saved sum, and, if it is, know we have found a subarray of size k. A hash map makes this lookup efficient.

大多数时候没错，找到合适的子数组后，我们可以执行 result ++ 。几乎总是 preSum 中的值将是 1 ，因此 result + = preSum.get（ sum-k）等于 result + = 1 或 result ++ 。

Most of the time you are right, upon finding an appropriate subarray we could just do result++. Almost always, the values in preSum will be 1, so result+=preSum.get(sum-k) will be equivalent to result+=1, or result++.

唯一的情况不是在 sum <上调用 preSum.put / code>之前已达到。如何获得我们已经拥有的和？唯一的方法是带负数（取消先前的数字），或带零（完全不影响总和）。

The only time it isn't is when preSum.put is called on a sum that has been reached before. How can we get back to a sum we already had? The only way is with either negative numbers, which cancel out previous numbers, or with zero, which doesn't affect the sum at all.

基本上，我们回到当子数组的总和等于0时，前一个 sum 。这样的子数组的两个示例是 [2，-2] 或琐碎的 [0] 。使用这样的子数组，我们需要将 1 添加到 result 作为 k + 2 -2 = k 或 k + 0 = k ，因此我们发现了多个子数组，其中一个是零和子数组（ sum = k + 0 ）和一个不带它（ sum = k ）。

Basically, we get back to a previous sum when a subarray's sum is equal to 0. Two examples of such subarrays are [2,-2] or the trivial [0]. With such a subarray, we need to add more than 1 to result as k+2-2=k or k+0=k, and thus we have found more than one subarray, one with the zero-sum subarray (sum=k+0) and one without it (sum=k).

这也是 preSum.put 中的 +1 的原因。每当我们再次达到相同的 sum 时，我们就会找到另一个零和数组。有两个零和子数组，我们有三个 sum = k 的子数组：原始数组（ sum = k ） ，原始文件加上第一个（ sum = k + 0 ），以及原始文件都包含两个原始文件（ sum = k + 0 + 0 ）。这种逻辑也适用于更多数目的零和子数组。

This is the reason for that +1 in the preSum.put as well. Every time we reach the same sum again, we have found another zero-sum array. With two zero-sum subarrays, we have three subarrays with sum=k: the original array (sum=k), the original plus the first (sum=k+0), and the original with both (sum=k+0+0). This logic holds for higher numbers of zero-sum subarrays as well.

这篇关于查找总和等于k的子数组的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！