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

一、题目

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

二、示例

2.1> 示例 1：

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

2.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的值，然后返回符合以上两个条件的所有子序列个数之和。对于这种与子序列元素统计相关的题目，我们通常第一想法就是通过双层遍历的方式进行计算：

【第1层循环】表示子序列的起始位置。 【第2层循环】表示子序列的结束位置。

但是，这种计算方式时间复杂度较高，我们其实还可以采用前缀和的方式进行计算。什么是前缀和呢？其实就是当我们需要计算集合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;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」