描述

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例

  1. 输入: nums = [1,1,1], k = 2
  2. 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
输入: nums = [1,2,3], k = 3
输出: 2

提示

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

解题思路

前缀和 + 哈希表优化

  1. 构建前缀和数组，以快速计算区间和
  2. 定义 pre[i] 为 [0..i] 里所有数的和，则 pre[i] 可以由 pre[i−1] 递推而来，即：pre[i]=pre[i−1]+nums[i]，不需要数组。
  3. 以 i 结尾的和为 k 的连续子数组个数时只要统计有多少个前缀和为 pre[i]−k 的 pre[j] 即可
  4. 建立哈希表 mp，以和为键，出现次数为对应的值，记录 pre[i] 出现的次数，从左往右边更新 mp 边计算答案
  5. 对于一开始的情况，下标 0 之前没有元素，可以认为前缀和为 0，个数为 1 个。

这类问题的一个关键点是，将思路转换为，以 i 结尾的个数有多少。因为这样考虑，不仅将问题剖解成子问题，而且在 i 之前的信息都是已知的，可以少讨论很多种可能。

代码

import java.util.HashMap;
import java.util.Map;

public class Solution {

    public int subarraySum(int[] nums, int k) {
        // key：前缀和，value：key 对应的前缀和的个数
        Map<Integer, Integer> preSumFreq = new HashMap<>();
        // 对于下标为 0 的元素，前缀和为 0，个数为 1
        preSumFreq.put(0, 1);

        int preSum = 0;
        int count = 0;
        for (int num : nums) {
            preSum += num;

            // 先获得前缀和为 preSum - k 的个数，加到计数变量里
            if (preSumFreq.containsKey(preSum - k)) {
                count += preSumFreq.get(preSum - k);
            }

            // 然后维护 preSumFreq 的定义
            preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1);
        }
        return count;
    }
}