LeetCode 560 Subarray Sum Equals K 题解前缀和 哈希表统计子数组和等于 k 的个数【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南围绕 LeetCode 560「和为 K 的子数组」Subarray Sum Equals K展开完整讲解从暴力枚举到前缀和 哈希表的两种解法、复杂度分析与常见陷阱并结合当前仓库中 Python、C、C、Java、Go、Rust、JavaScript、TypeScript、Kotlin、Swift 等 10 种语言的实现源码进行印证。读完本文你将掌握如何用 O(n) 时间统计和为 k 的连续子数组个数并能正确应对负整数、k 0等边界场景。前置知识在动手解决本题之前建议先熟悉以下两个基础工具前缀和Prefix Sum最优解依赖的核心性质——任意子数组的和都可以由两个前缀和相减得到。定义prefixSum[i]为数组前i个元素之和则下标从i1到j的子数组和为prefixSum[j] - prefixSum[i]。哈希表Hash Map用于存储前缀和 → 出现次数的映射实现在遍历过程中 O(1) 查询互补值curSum - k。解法一暴力枚举Brute Force思路最朴素的做法是枚举每一个可能的子数组检查其和是否等于k。对每个起始下标i我们逐元素向右扩展子数组同时维护一个运行中的累加和sum每当sum k就计数一次。注意本题要求的是连续子数组因此只需要双重循环即可覆盖所有区间。算法步骤初始化res 0。对每个起始下标i重置sum 0。对每个结束下标j从i到n - 1将nums[j]累加到sum。若sum kres加一。返回res。复杂度分析时间复杂度$O(n ^ 2)$枚举了所有 $\frac{n(n1)}{2}$ 个子数组。空间复杂度$O(1)$只使用了常数个变量。暴力法虽然直观但当n达到 $10^5$ 量级时 $O(n^2)$ 必然超时因此需要更优的解法。解法二前缀和 哈希表Hash Map思路核心洞察是若prefixSum[j] - prefixSum[i] k则从下标i1到j的子数组和为k。于是问题转化为遍历到每个位置j时统计此前有多少个位置i的前缀和等于curSum - k。用一个哈希表记录每个前缀和出现的次数即可在 O(1) 时间内完成查询。算法步骤初始化res 0、curSum 0以及哈希表prefixSums并预置{0: 1}表示空前缀前缀和为 0 出现一次。遍历数组中的每个数将其累加到curSum。计算diff curSum - k。将prefixSums[diff]即此前出现过diff这个前缀和的次数累加到res——这统计的是以当前位置结尾、和为k的子数组个数。将prefixSums[curSum]加一记录当前前缀和。返回res。复杂度分析时间复杂度$O(n)$数组只遍历一遍每次哈希表操作均为 O(1) 摊还。空间复杂度$O(n)$哈希表最多存储n 1个不同的前缀和。各语言实现对照本仓库在 10 种语言中提供了该解法的实现核心逻辑完全一致可直接对照学习Pythonpython/0560-subarray-sum-equals-k.py 使用字典dic {0: 1}预置空前缀遍历时先查sum - k再更新dic[sum]并注明 O(N) 时间、O(N) 空间。Ccpp/0560-subarray-sum-equals-k.cpp 使用unordered_mapint,int注意其额外在sum target时直接对count加一与mp[sum - target]的统计逻辑等价因为mp[0]尚未初始化时默认计数缺失需依赖预置的mp[0]实际上该实现以sum target显式补上从下标 0 开始的子数组这一情况。Cc/0560-subarray-sum-equals-k.c 展示了不依赖标准库哈希表时的完整手写实现定义Hash链地址法结构体INIT_HASH_SIZE 4096作为桶数HashKey通过取模把负前缀和归一化到桶内AddHash处理冲突、GetHash未命中返回 0主函数subarraySum同样先AddHash(hash, 0)预置空前缀再先查后插。这段代码对理解哈希表底层原理很有价值。Javajava/0560-subarray-sum-equals-k.java 使用HashMapInteger, IntegergetOrDefault(diff, 0)处理缺失键。Gogo/0560-subarray-sum-equals-k.go 用字面量map[int]int{0: 1}初始化。Rustrust/0560-subarray-sum-equals-k.rs 用HashMap::with_capacity(nums.len() / 2)预分配容量entry(...).and_modify(...).or_insert(1)完成计数更新。JavaScriptjavascript/0560-subarray-sum-equals-k.js 与TypeScripttypescript/0560-subarray-sum-equals-k.ts 使用Map以map.get(sum) || 0处理缺省值。Kotlinkotlin/0560-subarray-sum-equals-k.kt 使用hashMapOf(0 to 1)与getOrDefault。Swiftswift/0560-subarray-sum-equals-k.swift 使用字典[0: 1]与hashmap[diff, default: 0]。从上述实现可以看到无论语言如何算法骨架完全一致预置{0: 1}→ 累加curSum→ 查询curSum - k→ 更新curSum计数。常见陷阱Common Pitfalls陷阱一忘记用零初始化哈希表哈希表必须以{0: 1}作为初始状态用于处理从下标 0 开始的子数组。如果没有这一初始化那么从头开始的、前缀和恰好等于k的子数组将永远无法被计数。例如nums [3, 4, 7, 2]、k 7遍历到下标 1 时curSum 7需要diff 0存在才会计数[3, 4]这个子数组{0: 1}正是提供这个基准。陷阱二试图使用滑动窗口Sliding Window与乘积小于 K 的子数组这类单调性问题不同本题数组允许出现负数运行中的累加和并不单调收缩窗口可能让和变大也可能变小无法确定性地维护窗口。因此滑动窗口在这里失效必须采用前缀和 哈希表的方案。陷阱三先更新哈希表再查询操作的顺序至关重要必须先检查curSum - k是否在哈希表中然后再把curSum写入哈希表。若顺序颠倒当前元素会被错误地当作之前出现过的前缀和参与计数导致统计偏差。以k 0的场景为例若先写入curSum再查询curSum - 0 curSum会把空子数组也计入结果得到错误答案。举一反三边界与变式k 0且数组含零nums [1, -1, 0]、k 0时正确答案为 3子数组[1, -1]、[0]、[1, -1, 0]。用哈希表方案手工推演一遍即可验证{0: 1}初始化与先查后插顺序的必要性。答案上限子数组个数最多为 $\frac{n(n1)}{2}$当数组元素全为 0 且k 0时达到该上限因此res在 LeetCode 约束下需用int表示Python 无此顾虑。变式延伸同一套前缀和 哈希表思路稍加改造即可迁移到 subarray-sums-divisible-by-k改为对k取模、continuous-subarray-sum查找长度 ≥ 2 的倍数子数组等题目值得一并练习。小结解法时间复杂度空间复杂度适用场景暴力枚举$O(n^2)$$O(1)$数组规模小、仅用于理解题意前缀和 哈希表$O(n)$$O(n)$大规模数组含负数标准解法Subarray Sum Equals K 是前缀和 哈希表这一经典组合的入门必刷题它把一个看似需要枚举所有子数组的问题转化为统计互补前缀和出现次数的线性扫描问题。掌握{0: 1}初始化、先查询后更新这两个关键点并理解为什么负数使滑动窗口失效你就真正吃透了这道题也能为后续的子数组类问题打下坚实基础。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
