java - 查找总和等于 `k`的子数组的数量

Question

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

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

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。尽管代码在两种情况下均能完美运行，但我无法遵循其实际计算输出的方式。

我有两个具体的困惑点:

1)为什么代码会在不将其清零的情况下连续添加数组中的值？例如，如果[1,1,1,1,1]带有k=3，一旦sum=3，我们是否不需要将sum重置为零？是否不重置sum不会干扰以后的子数组的查找？

2)当我们找到sum result++的子数组时，我们是否应该简单地进行k？为什么我们改为添加preSum.get(sum-k)？

Answer 1

让我们先处理您的第一点困惑:

代码不断对数组求和并且不重置sum的原因是因为我们在进行过程中将总和保存在preSum(以前的总和)中。然后，无论何时我们到达sum-k是先前的总和(例如在索引i处)时，我们都知道索引i与当前索引之间的总和正好是k。

例如，在下面的图像中i=2，并且当前索引等于4，我们可以看到，由于9，所以当前索引的总和减去3，即索引i的总和就是6，即2和4(含)是6。



考虑这种情况的另一种方法是，从数组中丢弃[1,2](在我们当前的4索引处)会给我们一个总和6的子数组，其原因与上述类似(请参见图像)。

使用这种思维方法，可以说我们要从数组的前面丢弃，直到剩下sum k的子数组为止。我们可以这样说:对于每个索引，“只丢弃1，然后丢弃1+2，然后丢弃1+2+3等”(这些数字来自我们的示例)，直到找到一个总和k的子数组(在我们的示例中为k=6)。

这提供了一个完全有效的解决方案，但请注意，我们将在数组的每个索引处执行此操作，从而一遍又一遍地求和相同的数字。一种节省计算的方法是保存这些和以供以后使用。更好的是，我们已经将这些相同的数字求和以得到当前的sum，因此我们可以随便保存总数。

要找到一个子数组，我们可以浏览一下保存的总和，减去它们，然后测试剩下的是否是k。必须减去每个保存的和，这有点烦人，因此我们可以使用commutativity of subtraction来查看如果sum-x=k为true，那么sum-k=x也为true。这样，我们可以看到x是否是一个保存的和，如果知道，则知道我们找到了一个大小为k的子数组。哈希映射使此查找有效。

现在为您的第二个困惑点:

大多数时候，您是对的，找到合适的子数组后，我们可以做result++。几乎总是preSum中的值将是1，因此result+=preSum.get(sum-k)将等同于result+=1或result++。

唯一的不是在以前已到达的preSum.put上调用sum时。我们如何才能回到已经拥有的sum？唯一的方法是使用负数(可以抵消之前的数字)，或者使用零(完全不影响总和)。

基本上，当子数组的总和等于0时，我们回到上一个sum。此类子数组的两个示例是[2,-2]或琐碎的[0]。对于这样的子数组，当我们找到一个后来的，邻接的子数组sum k时，我们需要在1中添加多个result，因为我们发现了多个新的子数组，一个带有零和子数组(sum=k+0)，一个没有子数组(sum=k)。

这也是在+1中使用该preSum.put的原因。每当我们再次到达相同的sum时，我们就会发现另一个零和子数组。有两个零和子数组，找到一个带有sum=k的新相邻子数组实际上可以得到3个子数组:新的子数组(sum=k)，新的子数组加上第一个零和(sum=k+0)，以及原来的两个零和数(sum=k+0+0) 。该逻辑也适用于更多数量的零和子数组。