LeetCode—和为K的子数组（前缀和）

LeetCode—和为K的子数组（前缀和）

引用

CSDN

1.

https://blog.csdn.net/m0_62902381/article/details/140319523

题目描述

给你一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。

示例 1：

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

示例 2：

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

题目解析

这道题的描述很简单，也很好理解，目的就是让我们算出有多少个和为K的连续子数组。

因此最简单的一种方法就是暴力求解，找到所有的子数组，计算和是否为K。但是，暴力求解虽然简单，但是时间消耗是很大的，时间复杂度是n的平方。所有在数组很大时计算得会很慢。

因此我们可以使用另外一种方式来求解此题，可以思考一下，题目中让求的说连续的子数组和，可以通过前缀和的方式来表示。例如，求第3到5个数的和，就可以转化为前5个数的和减去前2个数的和，两个前缀和相减就可以来表示一个连续子数组的和。

借助官方题解中的一张图，在遍历结束后，会得到所有的前缀和及其出现的次数，在不断的遍历中pre-k会不断更新，在将其和前缀和去匹配，如果相等了count就加一。

用这种方法，只需遍历一次数组就可以实现，时间会大大减少。

代码如下：

public int subarraySum(int[] nums, int k) {
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    int pre = 0;
    int count = 0;
    for (int i = 0; i < nums.length; i++) {
        pre += nums[i];
        if (map.containsKey(pre - k)) {
            count += map.get(pre - k);
        }
        map.put(pre, map.getOrDefault(pre, 0) + 1);
    }
    return count;
}