图解LeetCode——560. 和为 K 的子数组

一、题目

给你一个整数数组 nums 和一个整数k ，请统计并返回 连续子数组中和为k的数量。

【输入】nums = [1,1,1], k = 2【输出】2

【输入】nums = [1,2,3], k = 3【输出】2

• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

根据主题描述，我们需要找到一个连续的子序列，总和等于K，然后返回所有符合上述两个条件的子序列的总数。对于这个与子序列元素统计相关的主题，我们的第一个想法通常是通过双层遍历来计算：

[第一层循环]表示子序列起始位置。[第二层循环]表示子序列结束位置。

然而，这种计算方法具有较高的时间复杂性，我们实际上可以使用前缀和计算方法。什么是前缀和前缀？事实上，当我们需要计算集合a[0]时、a[1]、a[2]……、a[i]当中子序列之和时，有以下规则：

【 计算a[0] 】sum(a[0]) = a[0]；【 计算a[0]~a[1] 】sum(a[1]) = a[1] + sum(a[0]) ；【 计算a[0]~a[2] 】sum(a[2]) = a[2] + sum(a[1]) ；【 计算a[0]~a[i] 】sum(a[i]) = a[i] + sum(a[i-1]) ；

假设我们的子序列不是从第一个元素开始的？例如，计算a[7]~a[9]子序列和。我们可以通过sum(a[9]) -sum(a[6])计算。这样做的好处是防止重复的遍历和计算。

然后，在理解了前缀和前缀之后，我们可以尝试回答这个问题。答案步骤如下：

[步骤1]遍历数组nums，并计算标i对应的前缀和preSum[i]；[步骤2]然后使用preSum[i]减去k值是我们仍然缺少的子序列总和(我们假设是x）；[步骤3]然后去map寻找它是否存在key值是x是的。如果不存在，则表示不匹配；如果存在，则获得相应的value值。其中，value值表示子序列总和为key子序列的次数。[步骤4]将value值累加到result上，当所有数组nums元素全部完成后，result值是最终的结果。

以上是解决这个问题的想法。为了便于理解，我们输入参数nums=[1,2,3]，k=3例如。具体处理过程如何，请参见下图所示：

class Solution {    public int subarraySum(int[] nums, int k) {        Map<Integer, Integer> map = new HashMap();        map.put(0, 1);        int result = 0;        int[] preSum = new int[nums.length + 1];        for (int i = 0; i < nums.length; i++) {            preSum[i + 1] = preSum[i] + nums[i];            result += map.getOrDefault(preSum[i + 1] - k, 0);            map.put(preSum[i + 1], map.getOrDefault(preSum[i + 1], 0) + 1);        }                     return result;    }}