Go实现LeetCode 560：前缀和+哈希表解决和为K的子数组

刷 LeetCode 的人应该都有个共同感受Hot 100 里的题表面上是一道一道的算法题实际上是帮你把数据结构与算法里的“套路”一个一个吃透。今天要聊的 560 题「和为 K 的子数组」是我个人非常推荐的一道题因为它把前缀和和哈希表这两个基础工具揉在一起做出了一种“降维打击”的解法。题目本身不难读但如果你第一次接触很可能会被 O(n²) 的暴力解卡住甚至不知道从哪下手。我这次用Go 语言来实现完整题解顺便把这题背后的“为什么”也掰开揉碎讲清楚希望帮你在 LeetCode 刷题路上少走几个弯路。这题的适用人群很广刚开始刷LeetCode 热门 100 题的初学者可以通过它理解“连续子数组”的经典处理思路已经有一定基础、准备面试的开发者也可以把它当作“前缀和 哈希表”这个组合套路的代表题来复习。下面我们从题目本身开始一步步拆解。1. 题目解读与核心考点1.1 题目重述与示例给你一个整数数组nums和一个整数k你需要统计和为 k 的连续子数组的个数。注意这里是“连续子数组”不是“子序列”。什么叫连续子数组就是数组中一段连续的元素比如数组[1, 2, 3]里[1, 2]是一个连续子数组[1, 3]不是因为它把中间的2跳过去了那就成了子序列问题处理方式完全不同。举个例子帮助你建立直觉输入nums [1, 1, 1]k 2输出2解释有两个子数组满足和为 2分别是[1, 1]下标 0~1和[1, 1]下标 1~2再看一个有正有负、更能说明问题的例子输入nums [1, 2, 1, -1, 2]k 3哪些子数组和为 3[1, 2]、[1, 2]从下标 2 开始的1, -1, 2不对是[1, -1, 2]那是 2。这里需要仔细算一下不如直接说我调试的时候常用的例子nums [1, -1, 0]k 0答案应该是 3因为[1, -1]、[0]、[1, -1, 0]这三段的和都是 0。1.2 核心考点子数组的“连续性”这道题考的不是你会不会用一个 for 循环求和而是你能不能抓住“连续”这两个字的数学表达。连续子数组的和天然适合用前缀和来表示。什么叫前缀和定义数组preSum[i]表示nums[0]到nums[i-1]的和特别地preSum[0] 0。那么preSum[i] nums[0] nums[1] ... nums[i-1]在这个定义下任意连续子数组nums[j..i]下标从 j 到 i包含两端的和可以写成sum(nums[j..i]) preSum[i1] - preSum[j]这是一个极其经典的恒等式几乎所有“连续子数组求和”类问题都可以从它出发。后面你会发现这个恒等式把“求一段连续区间的和”变成了“求两个前缀和之间的差”问题从二维区间求和变成了一维前缀和的比较。1.3 数据规模对解法的约束LeetCode 给的数据范围是1 nums.length 2 * 10^4-1000 nums[i] 1000-10^7 k 10^7这个规模很关键。如果数组长度只有二三百暴力两层循环没有任何问题怎么方便怎么来。但2 * 10^4的规模下两层枚举子数组端点就需要约n² / 2次计算也就是大约2 * 10^8次操作。在 Go 语言的 LeetCode 评测环境里这个量级大概率会超时虽然 Go 够快但 2 亿次循环加上内存访问已经逼近 1 秒的上限。所以我们必须想到更优的解法也就是下面要讲的“前缀和 哈希表”。2. 暴力解法先想通常规思路再谈优化2.1 暴力枚举的复杂度分析最容易想到的思路是枚举所有子数组的起点j和终点i再累加这段区间里的所有元素判断和是否等于k。三层的做法是外层循环枚举起点内层循环从起点向右扩展终点每次扩展时计算当前累加和仔细一看其实两重循环就够外层定起点j内层定义一个变量curSum每扩展一个位置i就curSum nums[i]然后判断curSum k。这样避免了第三层重复滚动求和把复杂度降到了 O(n²)。写成 Go 代码大概是func subarraySum(nums []int, k int) int { ans : 0 for j : 0; j len(nums); j { sum : 0 for i : j; i len(nums); i { sum nums[i] if sum k { ans } } } return ans }内层循环随着 j 向右移动不断累加不需要每次重新从 j 加到 i。但整体依然是 O(n²)因为内层循环总执行次数约为n² / 2。2.2 为什么暴力解法不够好从计算量到时间瓶颈我们直接用数据说话。当 n 2×10⁴ 时内层约执行2×10⁸次加法。现代 CPU 每秒能执行的普通整数加法大概在 10⁹ 量级但 LeetCode 的评测机需要同时运行大量测试用例实际分配给你的时间往往只有一秒左右。加上循环分支、计数器更新、内存读写2×10⁸次操作很可能在两三秒以上超时几乎必然。更重要的是面试官想看到的不是“能不能暴力解”而是你能不能把时间复杂度从 O(n²) 降到 O(n)。因为从暴力到高效中间藏着一个非常漂亮的数学转换那就是前缀和。2.3 用前缀和重新理解问题我们把暴力解法中“枚举起点 j”这件事换个视角。任意子数组nums[j..i]的和可以表示为preSum[i1] - preSum[j] k等价于preSum[j] preSum[i1] - k这意味着什么只要我们知道了当前下标i对应的前缀和preSum[i1]问题就变成了在这之前已经出现过的所有前缀和中有多少个等于preSum[i1] - k有多少个就有多少个以i结尾、和为 k 的连续子数组。这个转换直接把问题从“枚举子数组的起点”变成了“统计历史前缀和的次数”。枚举起点之所以慢是因为我们需要扫一遍区间内的所有元素而前缀和把连续区间的和信息压缩到了两个点的数值上。3. 哈希表降维打击的核心思路3.1 内层循环的本质一次“查找”回到刚才的结论对每一个当前位置i我们要找的是“历史前缀和中值为cur - k的那些点”。如果不用哈希表最直接的做法是维护一个数组存所有已经出现过的前缀和然后在数组中线性查找cur - k。这样外层循环 O(n)内层线性查找 O(n)总体又回到 O(n²)白忙活一遍。但你要是转念一想这不就是“查找一个值在集合里出现过多少次”吗哈希表的强项恰好是这个。在 Go 语言里map[int]int就是哈希表的标准实现它的平均查找和插入复杂度都是 O(1)。于是我们可以把“内层线性查找”直接优化成“一次哈希查询”整个算法从 O(n²) 降到了 O(n)。这张复杂度对比表可以看得很清楚解法时间复杂度空间复杂度适用规模双层枚举暴力O(n²)O(1)数组长度 10³ 左右前缀和 线性查找O(n²)O(n)效果同上没有实质提升前缀和 哈希表O(n)O(n)数组长度 2×10⁴ 轻松通过所谓“降维打击”就是内层循环不是被“优化”得更快而是被“消除”了。我们不再需要扫描历史前缀和只需要一次哈希问答。3.2 哈希表里存什么把“值”统计成“次数”一个常见误区是认为哈希表里只存“某个前缀和是否出现过”于是代码写成seen : map[int]bool{}如果你检查过几个例子就会发现这样会在某些 case 上少算。原因很简单数组里可能有负数同一个前缀和会重复出现多次而每一个出现位置都可能与当前i组成有效的子数组。举个例子nums [1, -1, 1, -1]前缀和序列含初始 0是0, 1, 0, 1, 0注意0和1都重复出现了。假设k 0当遍历到最后一个元素时前缀和又是 0此时历史中前缀和为 0 的点有三个初始位置、下标 2 处、下标 4 处之前我们需要按数组下标算清楚。如果用 bool 标记每一个前缀和只能记录 1 次必然漏掉很多。所以哈希表的 value 必须是“出现次数”也就是map[int]int。3.3 初始化map[0] 1的深刻原因这是整道题最容易踩的坑也是最值得展开的地方。前缀和数组通常这样定义preSum[0] 0表示空数组的前缀和。为什么要专门把它放进哈希表因为如果某个子数组正好从数组的 0 号位置开始比如nums [1, 2, 3]k 3那么[1, 2]从下标 0 开始它的和为 3。用前缀和怎么表达遍历到下标 1值为 2时当前前缀和cur 3我们需要找到一个历史前缀和pre满足cur - pre 3也就是pre 0。如果没有初始化map[0] 1这一步就会漏算。为什么初始时0的出现次数是 1因为“还没有任何累加时的前缀和”就是 0它是一个合法的、真实存在的前缀和。你完全可以把preSum[0] 0当作一个已经被“看到”过的点。如果你不初始化也可以在其他地方绕过去比如在循环前先存preSum[0]但那样逻辑容易乱。我的建议是固定写成preSumCount : map[int]int{0: 1}这是一个每个区间都可能用到的起跳点属于“背下来很容易理解很重要”的关键一行。4. Go 语言实现与实操细节4.1 完整代码与逐行解析下面是这道题的标准 Go 解法注释我写得很细方便你直接理解每一行的含义func subarraySum(nums []int, k int) int { // 记录“前缀和 - 出现次数”初始时前缀和 0 出现 1 次 preSumCount : map[int]int{0: 1} ans : 0 curSum : 0 for _, num : range nums { curSum num // 重点先查后更新 // 如果历史前缀和 pre 满足 curSum - pre k // 那么以当前位置结尾的、和为 k 的连续子数组就多出 preSumCount[pre] 个 ans preSumCount[curSum-k] // 再把这个前缀和的出现次数加一 preSumCount[curSum] } return ans }为什么“先查后更新”这么重要如果k 0当前前缀和curSum本身等于 0curSum - k 0如果先把preSumCount[curSum]再查询查询结果会把“空子数组”也就是当前位置自己和自己组成的子数组也算进去子数组长度至少为 1空子数组是不允许的于是答案就多了 1。每次遇到curSum 0的位置都会多算一次所以代码里一定要先执行查询、再更新计数。你可能会问Go 的map在 key 不存在时读出来是零值所以ans preSumCount[curSum-k]即使 key 不存在也只是加 0不会出错。这句话是对的但注意不要依赖它而忘记初始化{0: 1}因为 0 这个 key 是真实存在的需要显式声明出现次数为 1。4.2 为什么用map[int]int而不是其他容器在 Go 里哈希表就是map。底层是经典的桶数组结构负载因子超过一定阈值时会扩容平均情况下读写都是 O(1)。相比自己手写数组哈希、或者用slice线性扫map[int]int是这道题最自然的容器。有人可能会想前缀和的范围不是最大也就是2×10⁴ × 1000 2×10⁷左右吗能不能直接开一个大数组用前缀和的值当下标这样就省去哈希冲突的时间理论上可以但这个“值”可能是负数因为nums[i]最小是 -1000累加后可能出现负前缀和直接用数组下标还得做偏移麻烦不说还要浪费很多空间。map的 key 天然支持负数而且只存储真正出现过的前缀和空间复杂度与哈希表的大小成正比不会浪费。所以在 Go 里map[int]int是最合适的。4.3 边界条件与易错点清单我总结了一套自查清单写完代码后对照着检查一遍基本能避免所有坑初始化时有没有写0: 1这是漏掉“从下标 0 开始的子数组”的头号元凶。循环里是先查再更新还是先更新再查k 0时顺序错了直接崩。是否把子数组当成子序列如果题目改成“和为 k 的子序列”那是另一个动态规划问题不是这个解法。是否误以为数组全为正数就能用滑动窗口比如有些人看到“连续子数组”就想双指针滑动窗口但数组里有负数时滑动窗口的单调性不成立哈希表才是更通用的方案。如果你在本地跑测试建议多试几组带负数的输入比如nums [1, -1, 0]k 0期望结果应该是 3再试一组nums [0, 0, 0]k 0答案是 6三个单独 0两个连续 0一个整个数组。5. 常见问题与实战经验5.1 为什么不能用滑动窗口或双指针这是评论区高频问题。滑动窗口适用于“窗口内元素单调递增或递减”的场景也就是说右指针右移时窗口和变大左指针右移时窗口和变小我们才能通过收缩窗口来逼近目标。但当前数组里允许负数右指针右移时窗口和可能变小左指针右移时窗口和也可能变大窗口的“单调性”被打破了。强行滑动会导致大量漏算和重复计算。所以当你看到题目中数组元素可正可负时第一反应应该是前缀和 哈希表而不是滑动窗口。如果题目额外限定nums[i] 0那滑动窗口确实可行也更快。但 560 这道题没有这个限制我们还是老老实实用哈希表。5.2 与“两数之和”的关系一通百通做过 LeetCode 1. 两数之和 的人再回头看这道题会觉得特别亲切。两数之和要求在数组中找两个数a b target本质是“当前值 历史值 target”而本题中我们把数组换成前缀和数组问题就变成了“当前前缀和 - 历史前缀和 k”。两者都用了同一个哈希表套路边遍历边查表把历史信息存下来把两两组合的 O(n²) 问题降成 O(n)。如果你把前缀和数组求出来写一个“在这之前有没有出现过cur - k”的循环是不是就是两数之和的孪生兄弟所以强烈建议把这两道题放一起总结你会在“哈希表降维打击”这条路上走得更远。5.3 哈希表统计次数的意义重复前缀和前面已经说过数组里的负数会导致相同的前缀和多次出现。我再给一个更直观的例子。nums [1, -1, 1, -1, 1]前缀和包含初始 0为0, 1, 0, 1, 0, 1前缀和 1 出现了 3 次前缀和 0 出现了 3 次。如果我们统计 k 1 的子数组个数遍历到最后时curSum 1需要找历史中前缀和为 0 的点共 3 个说明以最后一个元素结尾、和为 1 的子数组就有 3 个。如果哈希表只存 bool这里只能给出 1直接漏了两个。这就是为什么 value 必须是int次数并且每次遍历到新的前缀和都要。6. 同类型题目的扩展与我的实操心得6.1 把套路迁移到更多题目前缀和 哈希表这个组合在 LeetCode 里是一整套方法论可以用到很多“连续子区间”相关的问题上统计「优美子数组」把奇数看成 1偶数看成 0就把问题转化为“和为 k 的子数组”。和可被 K 整除的子数组用前缀和对 K 取模再统计同余前缀和的个数。和相同的二元子数组本质和 560 一模一样的套路。路径总和 III树上的前缀和配合回溯撤销哈希表计数是这道题的进阶版。你会发现很多题目看起来复杂背后都是同一个核心思想用前缀和把区间和变成两点差再用哈希表把查历史降成 O(1)。6.2 刷题时的个人经验与调试建议我这道题第一次出错就栽在没初始化map[0] 1上。当时跑 LeetCode 的示例全对一提交就少算。后来用nums [1, 2, 3]k 3在纸上手动画了一遍流程才意识到第一个[1, 2]这个子数组对应的历史前缀和是 0而我从来没有把 0 存进哈希表。从那以后我学到一件事边界情况如果只靠看是看不出来的一定多造几个小例子把循环每一步的主变量变化写出来。还有一个调试技巧如果某个测试用例答案是 0 但你的程序返回 1通常就是“先更新再查”导致空子数组被纳入统计如果答案偏小通常就是漏掉0: 1或者误用了 bool 计数。这两个方向先排查效率极高。根据我自己的经验Go 语言实现这道题时还有一个隐藏的好处map读不存在的 key 返回零值使得ans preSumCount[curSum-k]这种写法非常简洁。但简洁不代表可以随意建议在代码注释里明确写一行“此处依赖 Go map 零值业务语义上必须先查后更新”防止后续维护的人误解。最后再分享一个小技巧如果你在面试中遇到这道题讲清楚思路比写出代码更重要。面试官不只想看你会不会背代码更希望听到你说清楚“为什么哈希表能把两层循环降成一维”。你只要把前缀和恒等式写出来再解释一遍cur - pre k本质上就已经赢了这道题。