【重点】【前缀和】560. 和为 K 的子数组-CSDN博客

文章介绍了两种使用哈希表的方法（前缀和和直接计算）来解决`subarraySum`问题，即找出数组中和为给定值k的连续子数组的个数。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

解法1：前缀和+哈希表

具体参见《算法小抄》。

Python

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        res = 0
        pre_sum = 0
        pre_dict = dict()
        pre_dict[0] = 1 # 前缀和 => 出现次数; 要想把任意子数组都表示成两个前缀和的差，
                        #必须添加pre_dict[0] = 1，否则当子数组是前缀时，没法减去一个数
        for i in range(len(nums)):
            pre_sum += nums[i]
            if pre_sum - k in pre_dict:
                res += pre_dict[pre_sum - k]
            pre_dict[pre_sum] = pre_dict.get(pre_sum, 0) + 1

        return res

Java

class Solution {
    public int subarraySum(int[] nums, int k) {
        int res = 0, preSum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 0; i < nums.length; ++i) {
            preSum += nums[i];
            if (map.containsKey(preSum - k)) { // 注意：这里只能是'-'
                res += map.get(preSum - k);
            }
            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }

        return res;
    }
}

解法2：哈希表

class Solution {
    public int subarraySum(int[] nums, int k) {
        int[] sumArray = new int[nums.length];
        Map<Integer, Integer> sumToCountMap = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            if (i == 0) {
                sumArray[i] = nums[i];
            } else {
                sumArray[i] = nums[i] + sumArray[i - 1];
            }
            int origin = sumToCountMap.getOrDefault(sumArray[i], 0);
            sumToCountMap.put(sumArray[i], origin + 1);
        }
        int res = sumToCountMap.getOrDefault(k, 0);
        for (int i = 0; i < sumArray.length; ++i) {
            int origin = sumToCountMap.get(sumArray[i]);
            if (origin > 1) {
                sumToCountMap.put(sumArray[i], origin - 1);
            } else {
                sumToCountMap.remove(sumArray[i]);
            }
            res += sumToCountMap.getOrDefault(sumArray[i] + k, 0);
        }

        return res;
    }
}