1. 题目背景与核心挑战这道来自力扣hot100的经典题目和为 K 的子数组LeetCode 560. Subarray Sum Equals K看似简单实则暗藏玄机。作为数组类问题的典型代表它考察的不仅是基础编程能力更是对算法优化思维的深度理解。题目要求很简单给定一个整数数组nums和一个整数k统计该数组中和为k的连续子数组的个数。比如nums [1,1,1]k2时返回2因为前两位和后两位的和都是2。但当你真正开始coding时会发现暴力解法在数据量稍大时就会超时。关键提示这道题O(n²)的暴力解法虽然直观但在力扣上会直接超时。必须找到O(n)或O(nlogn)的优化方案才能通过所有测试用例。2. 暴力解法与优化思路2.1 直观的暴力枚举法最直接的思路是双重循环枚举所有可能的子数组def subarraySum(nums, k): count 0 n len(nums) for i in range(n): sum 0 for j in range(i, n): sum nums[j] if sum k: count 1 return count这种方法时间复杂度O(n²)空间复杂度O(1)。当n10⁵时计算量将达到10¹⁰次操作远超力扣的时间限制。2.2 前缀和优化思路聪明的解法是利用前缀和Prefix Sum技巧。前缀和的定义是prefix[i]表示nums[0]到nums[i-1]的和。这样任意子数组nums[i..j]的和可以表示为prefix[j1] - prefix[i]。基于这个性质我们可以将问题转化为找到所有满足prefix[j1] - prefix[i] k的(i,j)对。这等价于寻找prefix[i] prefix[j1] - k。3. 哈希表优化实现3.1 算法核心思想使用哈希表存储前缀和的出现次数可以在O(1)时间内查询所需的前缀和值。具体步骤初始化哈希表prefix_sum {0:1}和为0出现1次维护当前前缀和current_sum遍历数组时计算current_sum nums[i]检查current_sum - k是否在哈希表中如果在则count prefix_sum[current_sum - k]更新current_sum的出现次数3.2 完整实现代码def subarraySum(nums, k): count 0 prefix_sum {0: 1} current_sum 0 for num in nums: current_sum num if (current_sum - k) in prefix_sum: count prefix_sum[current_sum - k] prefix_sum[current_sum] prefix_sum.get(current_sum, 0) 1 return count3.3 复杂度分析时间复杂度O(n)只需一次遍历空间复杂度O(n)最坏情况下需要存储n个不同的前缀和4. 边界条件与特殊测试用例4.1 必须考虑的边界情况空数组nums [], k0 → 返回0单个元素等于knums [1], k1 → 返回1多个相同元素nums [1,1,1], k2 → 返回2包含负数nums [-1,-1,1], k0 → 返回1k0的特殊情况nums [0,0,0], k0 → 返回64.2 测试用例验证表测试用例预期输出说明[1], 11单个元素[1,2,3], 32正常情况[1,-1,0], 03包含0和负数[0,0,0], 06全0数组[1], 00k0无解5. 算法优化技巧与心得5.1 关键优化点哈希表初始化必须包含{0:1}否则会漏算从数组开头开始的子数组更新哈希表应该在检查之后避免重复计数使用get方法可以简化代码避免KeyError异常5.2 常见错误排查错误忘记初始化{0:1}现象漏算从第一个元素开始的子数组示例nums [1], k1会返回0而不是1错误先更新哈希表再检查现象会错误计算空子数组示例nums [1], k0会返回1而不是0错误使用数组存储前缀和现象查找效率低导致超时解决方案必须使用哈希表实现O(1)查找5.3 性能优化实测在力扣平台上实测结果暴力解法在n20000时超时2000ms前缀和哈希表相同规模仅需40ms左右6. 同类问题扩展掌握了这个技巧后可以解决一系列类似问题最长的和为k的子数组LeetCode 325和为k的子矩阵LeetCode 1074乘积为k的子数组LeetCode 7130和1数量相等的子数组LeetCode 525这类问题的共同特点是都需要统计满足某种条件的连续子数组/子矩阵都可以通过前缀和/积哈希表的组合来优化都需要特别注意边界条件和初始化值7. 刷题策略建议对于力扣hot100这类高频题库先理解暴力解法确保完全掌握问题本质分析暴力解法的时间瓶颈在哪里寻找可以将O(n²)降为O(n)或O(nlogn)的数学性质或数据结构特别注意边界条件和特殊测试用例记录每种题型的解题模板形成肌肉记忆这道和为k的子数组作为hot100的经典题目几乎包含了数组类问题的所有考察要点。掌握它的优化思路后你会发现很多其他题目都是这个模式的变种。这也是为什么它会被选入hot100题库 - 它不仅考察编码能力更考察你能否从暴力解法中发现优化规律的能力。