和为 K 的子数组

LeetCode 560 题解：和为 K 的子数组。使用前缀和 + 哈希表优化，将时间复杂度从 O(n²) 降至 O(n)。

Leetcode Python 哈希表前缀和

阅读要点

暴力解法 O(n²) 存在重复计算
使用前缀和数组快速计算子数组和
哈希表记录前缀和出现次数，实现 O(n) 解法
注意使用字典而非集合，因为需要计数

题目

560. 和为 K 的子数组 - 力扣（LeetCode）

解答

思路

题目要求求子数组的和，常规思路是确定首尾然后求和，时间复杂度是O(n^2)。

在该方法中部分子数组的求和是完全重复的。

因此，我们可以借鉴动态规划的思路，在遍历的同时求前缀和数组。这样，想知道某个子数组的和只需要首尾对应的前缀和做差即可。

同时，我们还可以用前缀和来维护一个哈希表以便快速查询，注意只能用字典，不能用集合，因为需要记录之前pre[i] - k 在之前的前缀和中出现的次数。

答案

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        pre = [0] * (len(nums) + 1) # 前缀和
        pre_mp = collections.defaultdict(int) # 只能用字典，不能用集合，因为需要记录之前pre[i] - k 在之前的前缀和中出现的次数
        res = 0
        pre_mp[0] += 1
        for i in range(1, len(nums) + 1):
            pre[i] = nums[i-1] + pre[i-1]
 
            if pre[i] - k in pre_mp:
                res += pre_mp[pre[i] - k]
            
            pre_mp[pre[i]] += 1
 
            
 
        return res