【LC100】No560. 和为 K 的子数组

题目描述

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

子数组是数组中元素的连续非空序列。

提示:

• 1 <= nums.length <= 2 * 104

• -1000 <= nums[i] <= 1000

• -107 <= k <= 107

示例

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

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

链接

思路

一开始想用刚学会的滑动窗口做题，但发现题意不符合单调性，遂作罢。

其实暴力法就能做，枚举出所有子数组，然后判断是否为 k 即可。

但太暴力了，不够优雅。

连续子数组相关问题，我们也可以使用前缀和来考虑。

解法一：前缀和+哈希表

将问题转化为：令 i < j，判断 j 的前缀和减去 i 的前缀和，是否等于 k。

先遍历获得前缀和数组。

之后类似于两数之和，我们可以使用哈希表，用 O(1) 的时间获取信息。题目要求返回的是子数组个数，所以哈希表中只需要存放每个前缀和出现的次数即可。

有一个比较特殊的点在：

当 sum[i] == k 时，即前缀和等于 k 的时候，代表此时从 0 到 i 的数组和等于 k，此时 diff 为 0。

如果使用两数之和中 map.containsKey() 的判断，需要先给 map 单独添加 (0, 1) 的键值对。因为 map 中如果不包含 0 的情况，出现上述前缀和等于 k 的情况时，会漏掉计算。

在下方解法中，由于 sum 前缀和数组中有 sum[0] = 0 存在，在第二个循环中，会将 (0, 1) 这种情况在第一步就添加进 map 中。

代码

class Solution {
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int res = 0;
        int len = nums.length;
        // 设置sum[0] = 0，使sum[i]表示前i个元素的和
        int[] sum = new int[len + 1];
        for (int i = 0; i < len; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < len + 1; i++) {
            int diff = sum[i] - k;
            // 把map中不存在diff就不计算数量，转化为数量+0
            res += map.getOrDefault(diff, 0);
            map.put(sum[i], map.getOrDefault(sum[i], 0) + 1);

        }
        return res;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(n)