前缀和与哈希表：高效统计和为k的子数组

1. 题目解析与核心思路这道题目要求我们统计一个整数数组中所有和为k的连续子数组的个数。子数组必须是数组中连续的非空序列。我们先来看几个例子输入nums [1, 1, 1], k 2 输出2 解释[1,1]前两个元素和[1,1]后两个元素输入nums [1, 2, 3], k 3 输出2 解释[1,2]和[3]1.1 暴力解法分析最直观的解法是暴力枚举所有可能的子数组然后计算每个子数组的和是否等于k。具体实现可以用双层循环def subarraySum(nums, k): count 0 n len(nums) for i in range(n): current_sum 0 for j in range(i, n): current_sum nums[j] if current_sum k: count 1 return count这个解法的时间复杂度是O(n²)对于n2×10⁴的情况计算量约为2×10⁸次操作在LeetCode上会超时。1.2 前缀和优化思路为了优化时间复杂度我们可以使用前缀和Prefix Sum的概念。前缀和是指从数组开始位置到当前位置的所有元素之和。通过预处理计算前缀和数组我们可以将任意子数组的和表示为两个前缀和的差值sum(nums[i..j]) prefix[j1] - prefix[i]这样我们可以将问题转化为找到所有满足prefix[j1] - prefix[i] k的(i,j)对。2. 哈希表优化解法2.1 数学转换基于前缀和的概念我们可以将问题重新表述prefix[j1] - prefix[i] k⇒prefix[i] prefix[j1] - k这意味着当我们遍历数组计算前缀和时对于每个位置j我们只需要知道之前有多少个位置i的前缀和等于prefix[j1] - k。2.2 哈希表实现我们可以使用哈希表来记录每个前缀和出现的次数。具体步骤如下初始化哈希表prefix_count记录前缀和及其出现次数初始化prefix_sum 0和count 0遍历数组更新当前前缀和prefix_sum num检查prefix_sum - k是否在哈希表中如果在则增加对应的次数到count将当前前缀和存入哈希表更新出现次数from collections import defaultdict def subarraySum(nums, k): prefix_count defaultdict(int) prefix_count[0] 1 # 初始状态前缀和为0出现1次 prefix_sum 0 count 0 for num in nums: prefix_sum num count prefix_count[prefix_sum - k] prefix_count[prefix_sum] 1 return count2.3 关键点解析为什么初始化prefix_count[0] 1这是为了处理从数组开头到当前位置的和正好等于k的情况。例如当prefix_sum k时我们需要prefix_sum - k 0在哈希表中存在。为什么先查询再更新哈希表这样可以确保我们只统计之前出现的前缀和避免将当前前缀和与自己匹配这会导致统计长度为0的子数组。如何处理负数哈希表方法天然支持负数因为无论元素是正是负我们只关心前缀和之间的差值是否等于k。3. 复杂度分析时间复杂度O(n)我们只需要遍历数组一次每次哈希表的查询和插入操作都是O(1)空间复杂度O(n)最坏情况下需要存储n个不同的前缀和4. 边界条件与测试用例4.1 常见边界情况单元素数组nums [1], k 1→ 1nums [2], k 1→ 0全零数组nums [0,0,0], k 0→ 6所有可能的子数组都满足包含负数nums [1,-1,0], k 0→ 3[1,-1], [0], [1,-1,0]无解情况nums [1,2,3], k 10→ 04.2 测试代码test_cases [ ([1,1,1], 2, 2), ([1,2,3], 3, 2), ([1], 0, 0), ([1,-1,0], 0, 3), ([0,0,0], 0, 6), ([3], 3, 1) ] for nums, k, expected in test_cases: assert subarraySum(nums, k) expected, fFailed for {nums}, k{k} print(All test cases passed!)5. 实际应用场景这种前缀和哈希表的技巧在很多实际问题中都有应用金融分析找出股票价格累计变化等于某个目标值的时间段用户行为分析识别用户活跃度累计达到特定阈值的时间窗口资源监控检测服务器负载累计超过某个临界值的时段6. 常见错误与调试技巧6.1 常见错误忘记初始化prefix_count[0] 1 这会导致漏掉从数组开头到某个位置的子数组。更新哈希表的顺序错误 如果先更新哈希表再查询会错误地将当前前缀和与自己匹配。混淆子数组个数与存在性 哈希表需要记录出现次数而不仅仅是是否存在。6.2 调试技巧打印中间变量print(fnum{num}, prefix_sum{prefix_sum}, looking for {prefix_sum - k}) print(fCurrent count: {count}, prefix_count: {dict(prefix_count)})使用小规模测试用例手动验证 对于nums [1,1,1], k 2逐步检查每次迭代的状态。边界测试 特别关注空数组、单元素数组、全零数组等特殊情况。7. 算法变体与扩展7.1 最长和为k的子数组如果需要找到和为k的最长子数组的长度可以修改哈希表存储前缀和第一次出现的位置def maxSubArrayLen(nums, k): prefix_index {0: -1} max_len 0 prefix_sum 0 for i, num in enumerate(nums): prefix_sum num if prefix_sum - k in prefix_index: max_len max(max_len, i - prefix_index[prefix_sum - k]) if prefix_sum not in prefix_index: # 只记录第一次出现的位置 prefix_index[prefix_sum] i return max_len7.2 和为k的倍数的子数组LeetCode 974题要求统计和可被k整除的子数组数量。我们可以利用同余定理def subarraysDivByK(nums, k): prefix_mod defaultdict(int) prefix_mod[0] 1 prefix_sum 0 count 0 for num in nums: prefix_sum num mod prefix_sum % k count prefix_mod[mod] prefix_mod[mod] 1 return count8. 性能优化建议使用普通字典代替defaultdict 在性能敏感的场景可以使用普通字典配合get方法count prefix_count.get(prefix_sum - k, 0) prefix_count[prefix_sum] prefix_count.get(prefix_sum, 0) 1提前终止 如果k0且数组中没有0可以直接返回0避免不必要的计算。内存优化 对于非常大的数组可以考虑使用更紧凑的数据结构存储前缀和但通常哈希表已经足够高效。9. 面试技巧先讲暴力解法 展示你解决问题的基本思路然后指出其局限性。逐步优化 从暴力解法引出前缀和优化再进一步引入哈希表优化展示你的思考过程。强调关键点 特别说明prefix_count[0] 1初始化的原因和更新哈希表的顺序。准备测试用例 提前准备几个边界测试用例展示你的全面思考。讨论变体问题 展示你对类似问题的理解如最长子数组、可被k整除的子数组等。10. 总结前缀和哈希表是解决子数组和问题的强大工具可以将O(n²)的时间复杂度优化到O(n)。关键在于将子数组和问题转化为前缀和差值问题使用哈希表高效查询所需的前缀和正确处理边界条件和初始化状态注意更新哈希表的顺序以避免错误掌握这个技巧不仅能解决本题还能应对一系列类似的子数组和问题是算法面试中的必备技能。