10.和为K的子数组

560. 和为 K 的子数组

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

题解思路

1. 前缀和的概念
   什么是前缀和呢？前缀和是指数组中从第一个元素到当前位置的所有元素的累加和。例如，对于数组 [1, 2, 3]，前缀和就是：

• 前缀和[0] = 0（表示没有任何元素时的和）
• 前缀和[1] = 1（表示第一个元素的和）
• 前缀和[2] = 1 + 2 = 3（表示前两个元素的和）
• 前缀和[3] = 1 + 2 + 3 = 6（表示所有元素的和）

2. 哈希表的作用
   我们使用哈希表来存储每一个前缀和出现的次数，目的是为了快速查询某个前缀和是否存在，避免重复计算。

3. 算法步骤

初始化变量：

• count 用来记录符合条件的子数组的数量。
• preSum 用来保存当前的前缀和（即当前遍历到的位置的累加和）。
• map 用来记录每个前缀和出现的次数，初始时将 map.put(0, 1)，因为前缀和为 0 出现过一次（这个是为了考虑从数组的开头就符合条件的情况）。

遍历数组：

• 对每个元素 num，我们更新 preSum（即 preSum += num，计算当前的前缀和）。

检查是否存在符合条件的子数组：

• 我们判断当前的 preSum - k 是否在哈希表中出现过。如果出现过，说明存在一个子数组的和等于 k。这个子数组的起始位置就是哈希表中存储的 preSum - k 对应的前缀和位置。
• 如果存在，则把 map.get(preSum - k) 的值加到 count 上，这个值代表了出现过多少次 preSum - k，也就是说，找到了多少个和为 k 的子数组。

更新哈希表：

• 把当前的 preSum 存入哈希表 map，如果该前缀和已经出现过，则将其计数加 1；如果没有出现过，则初始化其计数为 1。

返回结果

最后，算法返回 count，即数组中和为 k 的子数组的个数。

图解前缀和

题解代码

/**
 * O（n2）时间复杂度高
 * @param nums
 * @param k
 * @return
 */
public int subarraySum(int[] nums, int k) {
    int count = 0;
    for (int start = 0; start < nums.length; start++) {
        int sum = 0;
        for (int end = start; end >= 0; end--) {
            sum += nums[end];
            if (sum == k) {
                count++;
                break;
            }
        }
    }
    return count;
}

/**
 * 前缀和 + 哈希表优化
 * @param nums
 * @param k
 * @return
 */
public int subarraySum(int[] nums, int k) {
    int count = 0;
    int preSum = 0; // 计算前缀和
    // 存放出现过的前缀和「key:前缀和，value:这个前缀和出现过多少次」
    Map<Integer, Integer> map = new HashMap<>();
    // 初始化map，前缀和为，出现过一次
    map.put(0, 1);
    for (int num : nums) {
        preSum += num; // 累加前缀和
        if (map.containsKey(preSum - k)) {
            // 如果出现过preSum-k的前缀和，则累加出现的次数
            count += map.get(preSum - k);
        }
        // 将当前前缀和存入map集合，如果原先map集合中存在，则累加value，否则value为1
        map.put(preSum, map.getOrDefault(preSum, 0) + 1);
    }
    return count;
}