查找总和等于“k”的子数组的数量

我们将得到一个整数数组和一个值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] with k=3 and [1,2,3,0,3,2,6] with k=6。虽然代码在这两种情况下都能完美运行，但我无法理解它实际如何计算输出。

我有两个具体的困惑点：

1）为什么代码不断地添加数组中的值，而不将其清零？例如，如果[1,1,1,1,1] with k=3, once sum=3，我们不需要重置吗sum为零？不重置sum干扰查找后面的子数组？

2）我们不应该简单地做result++当我们找到 sum 的子数组时k？为什么我们要添加preSum.get(sum-k)反而？

让我们先解决您的第一个困惑点：

代码不断对数组求和并且不重置的原因sum是因为我们将总和存入preSum（之前的总数）我们继续。然后，任何时候我们到达某个点sum-k是先前的总和（比如在索引处）i），我们知道总和between index i我们当前的索引正是k.

例如，在下图中i=2，我们当前的指数等于4，我们可以看到，自从9，当前指数的总和减去3，索引处的总和i, is 6, 指标之间的总和2 and 4（含）是6.

思考这个问题的另一种方式是看到丢弃[1,2]从数组（在我们当前的索引4) 给我们一个 sum 的子数组6，出于与上述类似的原因（详见图片）。

使用这种思维方法，我们可以说我们想要从数组的前面丢弃，直到剩下 sum 的子数组k。我们可以通过这样说来做到这一点：对于每个索引，“仅丢弃1，然后丢弃1+2，然后丢弃1+2+3等”（这些数字来自我们的示例），直到我们找到 sum 的子数组k (k=6在我们的例子中）。

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

要找到子数组，我们只需查看保存的总和，将它们相减并测试剩下的是否是k。必须减去每个保存的总和有点烦人，所以我们可以使用减法的交换律 https://en.wikipedia.org/wiki/Commutative_property看看如果sum-x=k是真的，sum-k=x也是如此。这样我们就可以看看是否x是一个保存的总和，如果是，就知道我们找到了一个大小为k。哈希映射使查找变得高效。

现在来说说你的第二个困惑点：

大多数时候你是对的，在找到合适的子数组后，我们可以这样做result++。几乎总是，值preSum将1, so result+=preSum.get(sum-k)将相当于result+=1, or result++.

唯一不是的时候是preSum.put被称为sum之前已经达到了。我们怎样才能回到sum我们已经有了？唯一的方法是使用负数，这会抵消之前的数字，或者使用零，这根本不会影响总和。

基本上，我们回到了之前的状态sum当子数组的总和等于 0 时。此类子数组的两个示例是[2,-2]或琐碎的事[0]。对于这样的子数组，当我们找到一个稍后的、具有 sum 的相邻子数组时k，我们需要添加超过1 to result因为我们发现了不止一个新子数组，其中一个是零和子数组（sum=k+0）和一个没有它的（sum=k).

这就是原因+1 in the preSum.put以及。每次我们都达到相同的目标sum我们再次发现another零和子数组。对于两个零和子数组，找到一个新的相邻子数组sum=k实际上给出了 3 个子数组：新的子数组 (sum=k)，新子数组加上第一个零和 (sum=k+0），以及具有两个零和的原始数据（sum=k+0+0）。此逻辑也适用于更多数量的零和子数组。