寻找和为 `k` 的子数组数量

Question

寻找和为 `k` 的子数组数量

9

我们将获得一个整数数组和一个值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) 当我们找到一个和为k的子数组时，我们不应该只需执行result++吗？为什么要添加preSum.get(sum-k)？

- user8177388

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- River · Accepted Answer

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

代码不断对数组求和而不重置sum的原因是，我们在进行操作时将总和保存在preSum（之前的总和）中。然后，每当我们到达一个点，sum-k是一个先前的总和（例如在索引i处），我们就知道索引i和当前索引之间的总和恰好为k。

例如，在下面的图像中，当i=2，当前索引等于4时，我们可以看到，由于9，即当前索引处的总和，减去i处的总和3，得到6，即索引2和4（包括）之间的总和为6。

另一种思考方式是，将数组中的[1,2]（在当前索引4处）丢弃，这样我们就得到了一个和为6的子数组，原因与上面类似（详见图像）。使用这种思考方法，我们可以说要从数组前面丢弃，直到剩下一个和为k的子数组。我们可以这样做：对于每个索引，"仅丢弃1"，然后"丢弃1+2"，然后"丢弃1+2+3"等（这些数字来自我们的例子），直到找到和为k的子数组（在我们的例子中，k=6）。这给出了一个完全有效的解决方案，但请注意，我们将在数组的每个索引处执行此操作，因此反复求和相同的数字。节省计算的方法是保存这些和以供稍后使用。更好的是，我们已经对这些相同的数字进行求和，以获得当前的sum，因此我们可以在进行时保存该总数。

要找到一个子数组，我们可以浏览保存的总和，减去它们并测试剩余的是否为k。每次都要减去每个保存的总和有点麻烦，所以我们可以使用减法的可交换性来看到如果sum-x=k是真的，sum-k=x也是真的。这样，我们只需要查看x是否为已保存的总和，如果是，则知道我们已经找到了大小为k的子数组。哈希映射使此查找高效。

现在让我们来解决你的第二个困惑：

大多数情况下，你是正确的，找到合适的子数组后，我们可以只做result++。几乎总是，preSum中的值将为1，因此result+=preSum.get(sum-k)将等同于result+=1或result++。

唯一不是这样的情况是当对一个已经到达的sum调用preSum.put时。我们如何回到已经存在的sum？唯一的方法是使用负数，它们会取消前面的数字，或者使用零，它根本不影响总和。

基本上，当子数组的总和等于0时，我们会回到先前的sum。这种子数组的两个示例是[2，-2]或微不足道的[0]。对于这样的子数组，当我们找到后来的相邻子数组的总和为k时，我们需要将result加1以上，因为我们已经找到了一个以上的新子数组，一个是带有零总和的子数组（sum=k+0），另一个是没有零总和的子数组（sum=k）。

这也是在 preSum.put 中加入 +1 的原因。每当我们再次到达相同的 sum 时，我们就会发现另一个零和子数组。有了两个零和子数组，找到一个新的相邻子数组，其 sum=k 实际上会给出 3 个子数组：新的子数组（sum=k），新的子数组加上第一个零和（sum=k+0），以及带有两个零和的原始子数组（sum=k+0+0）。这种逻辑也适用于更高数量的零和子数组。