前缀和与哈希表解决子数组和问题
1. 题目解析与核心思路560.和为K的子数组这道题在LeetCode上属于中等难度但它的解题思路非常经典涉及算法面试中的高频考点。题目要求我们找出数组中所有连续子数组的和等于给定值k的情况数量。我第一次遇到这个问题时最直观的想法是暴力枚举所有可能的子数组然后计算它们的和。这种方法的时间复杂度是O(n²)对于小规模数据尚可接受但当数组长度达到10⁵级别时就会超时。后来通过学习掌握了更高效的前缀和哈希表解法将时间复杂度优化到O(n)。2. 前缀和与哈希表的精妙结合2.1 前缀和概念解析前缀和是一种预处理技术它通过计算数组从起始位置到当前位置的元素和将子数组求和问题转化为前缀和的差值问题。定义前缀和数组prefix其中prefix[i]表示nums[0]到nums[i-1]的和。举个例子对于数组[1,2,3]其前缀和数组为[0,1,3,6]。注意我们通常会在前缀和数组开头添加一个0这样可以统一处理从数组第一个元素开始的子数组。2.2 哈希表的优化作用单纯使用前缀和仍然需要双重循环来比较所有可能的子数组和。这时候哈希表就派上用场了——我们可以用哈希表记录每个前缀和出现的次数这样在遍历时就能快速查询到需要的互补值。具体来说当我们计算到prefix[j]时想要找到之前出现过的prefix[i]使得prefix[j] - prefix[i] k。这等价于寻找prefix[i] prefix[j] - k。哈希表可以帮助我们在O(1)时间内完成这个查询。3. 详细实现步骤与代码解析3.1 算法实现步骤初始化哈希表记录前缀和为0出现的1次base case初始化当前前缀和sum和结果计数器count遍历数组计算当前前缀和sum nums[i]检查sum - k是否在哈希表中如果在则count map[sum-k]将当前sum存入哈希表如果已存在则递增计数返回最终的count值3.2 C代码实现class Solution { public: int subarraySum(vectorint nums, int k) { unordered_mapint, int prefixSum; prefixSum[0] 1; int sum 0, count 0; for (int num : nums) { sum num; if (prefixSum.find(sum - k) ! prefixSum.end()) { count prefixSum[sum - k]; } prefixSum[sum]; } return count; } };3.3 关键点解析哈希表初始化时为什么要放prefixSum[0]1 这是为了处理从数组第一个元素开始的子数组。当子数组从index0开始时它的和就是prefix[j]-0k。为什么是count prefixSum[sum-k]而不是直接count 因为可能有多个位置的前缀和相同每个都能与当前sum构成满足条件的子数组。4. 复杂度分析与边界情况4.1 时间复杂度构建前缀和O(n)哈希表操作每次查询和插入都是O(1)总体时间复杂度O(n)4.2 空间复杂度哈希表存储前缀和最坏情况下需要存储n个不同的前缀和空间复杂度O(n)4.3 边界情况处理空数组直接返回0所有元素相同且等于k注意子数组长度可以是1到n数组中存在负数这是使问题复杂化的关键也是暴力法失效的主要原因5. 实战技巧与常见错误5.1 调试技巧当你的代码出现错误时可以打印出遍历过程中的sum值每次查询sum-k的结果哈希表的实时状态5.2 常见错误忘记初始化prefixSum[0]1先更新哈希表再查询应该先查询再更新使用int导致溢出当k很大或很小时错误地认为数组元素都是正数而尝试用滑动窗口5.3 性能优化对于C使用unordered_map而不是map因为前者平均O(1)的查询时间可以省略显式的前缀和数组只维护一个累加变量对于Python使用defaultdict(int)可以简化代码6. 相关题目拓展掌握了这道题的解法后可以尝试解决以下类似问题325.和等于k的最长子数组长度523.连续的子数组和974.和可被K整除的子数组1248.统计优美子数组这些题目都在不同程度上使用了前缀和哈希表的技巧但各自有一些变形和额外的条件限制。通过对比练习可以更深入地理解这个解题范式的应用场景。
