代码随想录算法训练营刷到第六天哈希表 part02算是第一次把“哈希”两个字从模板刷成了思维。前一天的四道题——有效的字母异位词、两个数组的交集、快乐数、两数之和——本质上都在问“这个元素出现过没有、出现了几次”一道图省事的 HashMap 就能全部带过。但进入 part02 之后题风突变454 四数相加 II 要统计的是组合数量383 赎金信考验的是计数不能被重复使用而 15 三数之和和 18 四数之和干脆搬出了排序加双指针让不少人当场怀疑自己是不是进错了章节。这篇东西不是复述题解而是把我刷这一天时真正卡住过的点、推翻过的思路、以及最后沉淀下来的调试套路一次讲完。无论你是刚跟着训练营走到 Day6还是回头补哈希表的短板这一篇应该都能帮你少走几步弯路。题量不大四道题但每一道都在提醒同一件事哈希表不是“万能计数神器”选对数据结构、选对解法思路比闷头把 Map 塞进所有场景重要得多。1. Day6 的题单逻辑为什么这四道题凑成了一天1.1 从“查在不在”升级到“数次数、找配对”如果只看题面这四道题好像没啥联系一个是在四个数组里找和为 0 的组合数一个是判断字符串 A 能否由字符串 B 的字符拼出来两个则是找数组内多个元素之和等于目标值的组合。但把它们放到一起其实是哈希表应用场景的一次完整进阶。part01 的四道题解决的都是“存在性问题”这个数有没有出现过、这个字母在不在、这个数之前见没见过。到了 part02问题统一变成了“要多少次、有几种、去重后还剩哪些”这就迫使你从结果倒推解法。454 需要知道某个两数之和已经出现了多少次所以用 Map 做计数器383 需要知道字符还剩余几个可用所以用数组模拟计数15 和 18 则要保证输出结果不重复单纯的哈希查找能解但去重逻辑能把人绕晕最终最优解是排序加双指针。我整理了一张表方便你直观看到四道题的定位差异题目核心问法推荐数据结构时间复杂度454 四数相加II四个数组各取一个数和为 0 的组合数量HashMap 计数O(n²)383 赎金信magazine 能否覆盖 ransomNote 的所有字符int[26] 数组计数O(mn)15 三数之和数组内三个数和为 0结果集合不重复排序 双指针O(n²)18 四数之和数组内四个数和为 target结果集合不重复排序 双指针O(n³)把这四道题放在同一天还有一个隐性的教学目的让你看清“哈希表能做”和“哈希表该做”是两回事。454 和 383 用哈希计数是优雅的15 和 18 却更适合双指针这个对比本身就是宝贵经验。1.2 三数之和、四数之和为什么会被归到哈希表章节很多人第一次看到 Day6 题单时会愣一下三数之和不是经典双指针题吗怎么算哈希表 part02其实这得从题目的血缘说起。两数之和是哈希表的经典应用用 Map 记录已经遍历过的数实现在 O(n) 时间内找到配对数。三数之和像极了“两数之和的二维版本”固定一个数后剩余问题就变成找两个数和为指定值哈希表确实可以做。但三数之和要求去重如果我把固定过的数存进 Map再去找两个数的组合最后还需要对三元组排序去重一个不小心就会把同一组答案统计多次。代码写出来少说四五十行中间全是边界判断。代码随想录把这两道题放在哈希表章节我认为是想用“对比”来加深理解同一道题哈希解法能跑通但繁琐双指针解法简洁高效。这样当你下次看到“找若干个数满足条件”的题时就会下意识先想一遍“排序后能不能用双指针”而不是无脑掏 HashMap。数据结构是工具不是信仰这个道理刷完这一天自然会懂。2. 454 四数相加II与383 赎金信把哈希当计数器用2.1 454 的关键转折把 O(n⁴) 拆成两个 O(n²)454 的暴力思路很直接四层循环遍历四个数组复杂度 O(n⁴)。如果 n 是 200那就是 16 亿次运算跑起来会非常吃力。优化的核心在于“两个两个处理”。具体做法分两步遍历 nums1 和 nums2 的所有组合把两数之和作为 key出现次数作为 value 存进 HashMap。再遍历 nums3 和 nums4 的所有组合目标值就是0 - (c d)直接从 Map 里取对应次数累加进答案。这里最容易搞错的一个点是为什么 Map 里要存“次数”而不是只存“是否存在”因为同一个两数之和可能由多组不同的 (a, b) 产生比如 nums1[1,2]nums2[-1,-2]两数之和 0 可能对应 (1,-1) 和 (2,-2) 两组。如果只记录布尔值那后半段遍历时会漏掉大量组合。这一点和 part01 的两数之和不太一样那题只问是否存在这题问的是数量。参考实现def fourSumCount(nums1, nums2, nums3, nums4): sum_map {} for a in nums1: for b in nums2: key a b sum_map[key] sum_map.get(key, 0) 1 count 0 for c in nums3: for d in nums4: target -(c d) if target in sum_map: count sum_map[target] return count时间上两段二重循环都是 O(n²)总复杂度 O(n²)空间复杂度也是 O(n²)因为最坏情况下前两组的所有和都可能不相同。LeetCode 原题 n 不超过 200O(n²) 完全可接受这也是“空间换时间”的一个典型实例把前一半的枚举结果存起来后一半枚举时直接查表。顺带提一个使用getOrDefault的注意点很多语言里如果 key 不存在会返回 null 或 0写不好可能抛异常或者漏加。Python 里推荐用get(key, 0)Java 里推荐getOrDefault(key, 0)一定要给默认值。2.2 383 的字符计数int[26] 为什么优于 HashMap383 的题意翻译成人话就是用 magazine 里现成的字母去拼 ransomNote每个字母只能用一次。这题和 242 有效的字母异位词非常像都是“统计字符串中每个字母个数”但 242 是双向比较相同383 是单向覆盖。解法很成熟先遍历 magazine用长度为 26 的数组记录每个小写字母的出现次数再遍历 ransomNote每遇到一个字母就把对应计数减一如果减完发现小于 0说明 magazine 里的字母不够用直接返回 false。def canConstruct(ransomNote: str, magazine: str) - bool: record [0] * 26 for ch in magazine: record[ord(ch) - ord(a)] 1 for ch in ransomNote: index ord(ch) - ord(a) record[index] - 1 if record[index] 0: return False return True那问题来了为什么用 int[26] 而不是 HashMap因为题目明确说了字符串只包含小写字母字符集是固定的、数量有限的 26 个用数组的话索引计算快访问是 O(1)空间又是常数级 O(1)。HashMap 虽然也能做但涉及哈希计算和自动装箱常数更大代码也更啰嗦。反过来如果字符集扩大到 Unicode或者字符串里可能包含任意字符int[26] 就不够用了这时用 HashMap 才是合理的。这就是数据结构和场景匹配的问题也是 242、383 这类题反复训练的核心点。另外注意这道题的判断顺序不能反。必须先统计 magazine再消耗给 ransomNote。如果先统计 ransomNote再判断 magazine 够不够逻辑上也能实现但代码会更绕。官方题解里只给了一个方向实际写的时候保持“先备货后消耗”的思路不容易出错。2.3 为什么这两题放到一起刷效果最好454 和 383 虽然一个处理数字一个处理字母但底层都是“计数 查表”。454 把四个数组拆成两两一组本质上是把复杂问题的维度降低一半383 把字符出现次数做成数组本质上是把“可变大小的哈希”简化成“固定大小的桶”。两道题连刷你会自然形成一种条件反射遇到需要统计出现次数的问题先想“计数器是什么形态”——是定长数组还是动态 Map还是别的结构。这个条件反射在后续很多题里都有用比如滑动窗口里的字符频次、前缀和加哈希表统计子数组个数都会用到类似套路。刷题的经验积累并不只是记住几道题而是把“什么时候用哪种结构”的判断练成肌肉记忆。3. 15 三数之和哈希的“劝退课”与双指针的入场3.1 哈希解法的去重困境三数之和的题面就一句找出数组中和为 0 的三个数不能重复。如果只问“有没有”那哈希解法很简单——两层循环枚举前两个数第三个数去 Map 里查。但偏偏要“结果不重复”这就非常麻烦了。举个具体的例子排序后的数组是[-1, -1, 0, 1, 2]固定第一个 -1 时可能找到[-1, -1, 2]和[-1, 0, 1]。如果不小心把固定数去重逻辑写成“当前数等于下一个数就跳过”那个合法的[-1, -1, 2]就会被误杀。更麻烦的是如果你把查到的第三个数也存进 Map那同一个三元组可能被多个“前两数组合”重复命中最后要么用 Set 暴力去重要么在循环里写完一堆“前一个 后一个”的判断。即使写对了代码的复杂度也是一眼难尽面试现场很容易翻车。哈希解法的最大问题不在于“能不能算对”而在于“去重逻辑的复杂度太高”错误率直线上升。所以三数之和的推荐解是排序加双指针。排序把无序数组变成有序双指针则能在 O(n) 内搞定“固定一个数后的两数查找”整体复杂度 O(n²)空间复杂度 O(1)还天然规避了去重地狱。3.2 排序 双指针的核心与去重三原则先排序然后外层固定一个数 i内层用 left 和 right 两个指针从剩余区间的两端向中间逼近。三数之和大于 0 就右指针左移小于 0 就左指针右移等于 0 就记录答案并收缩两端。这里面有三个去重原则少一个都会出问题。第一个原则是外层固定数去重if i 0 and nums[i] nums[i-1]: continue这里必须和前一个数比较而不是和后一个数比较。原因在于如果当前固定数和前一个固定数相同那当前 i 能探测到的所有组合在前一个 i 时已经全部探测过了因为后续区间只会更小。但如果用nums[i] nums[i1]去跳过就会误伤 left 指向 i1 的情况。还是那个老例子[-1, -1, 2]i0、left1 时正好组成合法答案你跳到 i1 就会发现 left2这个组合永远找不到了。第二个原则是左指针去重发生在记录答案之后while left right and nums[left] nums[left 1]: left 1第三个原则是右指针对称去重while left right and nums[right] nums[right - 1]: right - 1这两个去重的目的都是为了避免同一个 i 下left 或 right 移动到和已记录结果相同的数值上。和固定数去重的时机不同指针去重必须在“已经找到一个答案”之后再做。如果还没找到答案就提前跳重复值可能会把能组成答案的左指针或右指针跳过去反而漏解。完整代码def threeSum(nums): nums.sort() n len(nums) res [] for i in range(n - 2): if nums[i] 0: break if i 0 and nums[i] nums[i - 1]: continue left, right i 1, n - 1 while left right: total nums[i] nums[left] nums[right] if total 0: right - 1 elif total 0: left 1 else: res.append([nums[i], nums[left], nums[right]]) while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 return res3.3 复杂度推导与剪枝细节外层 i 循环需要走到n - 2因为后面至少得留两个位置给 left 和 right。内层 while 最多把整个剩余区间扫一遍所以是 O(n)总复杂度 O(n²)。排序那部分用的是语言内置排序通常 O(n log n)不会改变整体的 O(n²)。这里有一个容易被忽略的剪枝if nums[i] 0: break。因为数组已经排序过i 是最小元素如果最小元素都大于 0那三数之和必然大于 0后面的数只会更大所以可以直接终止整个循环。同理如果nums[i] nums[i1] nums[i2] 0也可以提前 break不过这个剪枝可写可不写。倒是nums[i] 0这个判断非常直观几乎不增加代码量还能省掉大量无效扫描建议保留。刷这道题时我犯过的一个典型错误是在 while 循环里找到答案后只做left 1忘了同时right - 1结果造成死循环。原因很简单记录答案后如果不收缩两端下一轮又会在同样的位置重逢。后来我养成了一个习惯找答案后先做两个去重 while再同步移动两个指针这个公式化写法非常稳。4. 18 四数之和双指针的进阶版剪枝才是细节怪4.1 从三数之和到四数之和的扩展套路18 题的思路是 15 题的直接扩展外面套两层固定循环内层还是双指针。15 是一个外层循环加双指针18 就多加一个外层循环整体变成一个“固定 i 固定 j 双指针”的三层结构。def fourSum(nums, target): nums.sort() n len(nums) res [] if n 4: return res for i in range(n - 3): if i 0 and nums[i] nums[i - 1]: continue for j in range(i 1, n - 2): if j i 1 and nums[j] nums[j - 1]: continue left, right j 1, n - 1 while left right: total nums[i] nums[j] nums[left] nums[right] if total target: right - 1 elif total target: left 1 else: res.append([nums[i], nums[j], nums[left], nums[right]]) while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 return res去重逻辑和三数之和一脉相承第一层固定数用nums[i] nums[i-1]跳过第二层固定数用nums[j] nums[j-1]跳过注意 j 的起始位置是i1所以去重条件要写成j i1否则 j 第一次等于 i1 时比较nums[j]和nums[j-1]会误判。双指针的去重时机同样放在找到答案之后。4.2 剪枝的边界问题不能照搬三数之和的三板斧很多人在四数之和这里直接套用“最小数大于 target 就 break”结果在小数据上发现答案错了。为什么会错三数之和的 target 固定是 0排序后如果首元素大于 0后面都是正数和必然大于 0可以安全 break。但四数之和的 target 可以是任意整数甚至可以是一个负数。举个最直观的反例nums [-5, -4, -3, 1]target -11排序后首元素是 -5它大于 -11但四个数相加-5 (-4) (-3) 1 -11完全合法。如果写“nums[i] target就 break”这个答案就漏掉了。所以四数之和里不能做这个剪枝至少不能无条件做。正确的剪枝姿势有两组第一组剪枝在 i 层如果nums[i] nums[i1] nums[i2] nums[i3] target说明当前 i 之后的所有组合里取前四个最小数都已经超过 target再往后只会更大直接 break。如果nums[i] nums[n-3] nums[n-2] nums[n-1] target说明当前 i 能取到的最大四数之和都小于 target那这个 i 可以不看了continue 换下一个 i。第二组剪枝在 j 层如果nums[i] nums[j] nums[j1] nums[j2] targetbreak。如果nums[i] nums[j] nums[n-2] nums[n-1] targetcontinue。这两组剪枝的道理是一样的先看“固定位置下能达到的最小四数和”和“最大四数和”如果最小值都超了后面不用看如果最大值都不够当前固定数可以直接换下一个。它们的作用不是改变复杂度量级而是让常数小很多。实测数据中这类剪枝能让耗时从几百毫秒降到几十毫秒尤其在大数组上非常明显。4.3 四重去重和整数溢出两个最容易翻车的点去重层面18 题比 15 题多一层固定数也就多一处去重。四个维度的去重都不能少i 去重、j 去重、left 去重、right 去重。漏掉任何一个结果里都会出现重复四元组。还有一个 C 选手更容易踩的坑int 溢出。LeetCode 上 18 题的元素范围是[-10^9, 10^9]四个数求和最大可能到 4×10^9已经超过 32 位 int 的上限约 21.47 亿。所以在 C 里如果直接用nums[i] nums[j] nums[left] nums[right]做 int 加法再和 target 比较溢出后会出现意想不到的错误。正确做法是把结果转成 long long或者直接在比较时写(long long)nums[i] nums[j] nums[left] nums[right] target。用 Python 的同学在这个问题上会轻松一些因为 Python 的 int 是任意精度的不会溢出。但如果你最终面试用 C 或 Java一定要记得这个细节。很多训练营同学用 Python 刷题通过后换到 C 提交同样的逻辑就 WA 了绝大多数就是溢出问题。5. 刷题实录高频踩坑与 Debug 思路5.1 我实际看到的三个最常见的错误把这一天刷完我回看了不少训练营同学的报错记录也翻了自己初刷时的代码发现高频错误高度集中在这三个地方。整理成表格方便你对照自查错误现象典型错误写法正确写法原因454 结果偏小用 HashSet 记录两数之和HashMap 记录两数之和及次数同一个和对应多组数对set 会丢计数15 漏掉合法三元组if nums[i] nums[i1]: continueif i0 and nums[i]nums[i-1]: continue跳过 i 的同时会误伤 lefti1 的组合18 结果总少几组直接if nums[i] target: break用最小四数和/最大四数和剪枝target 为负数时首元素大于 target 不代表无解这三个错误基本覆盖了这天最核心的坑位。尤其是第一个我见过太多人把 454 想成“是否存在”而不是“有多少种”一旦思路歪了后面怎么调都不对。5.2 自己调试的两个小技巧第一个技巧是“打印排序后的数组”。三数之和、四数之和这类双指针题90% 的异常行为都和排序结果有关。我调试时会在排序后立刻print(nums)然后手动模拟一遍双指针移动先确认自己的预期再去比对代码。很多时候错误一眼就能看出来比自己盯着代码干想快得多。第二个技巧是“写个暴力解法做对拍”。454 可以用四层循环对拍三数之和可以用三层循环加 Set 去重后对拍。小数据量下暴力结果一定是正确的拿它和双指针解法的输出做对比就能精确定位到是哪一步逻辑出错。LeetCode 本身会帮你测试但刷题复盘时做本地对拍能让你更快找到错误的根源而不是蒙一个边界条件再提交一次。5.3 训练营节奏下如何高效吸收这四道题代码随想录训练营的节奏是每天固定题量打卡压力其实是存在的。我的建议是第一天先把每道题的题解看明白能凭理解写出核心骨架第二天完全不看题解重新独立写一遍卡住的地方就是你的薄弱点等到周末再做一次二刷重点看之前卡住的那几个点。不要追求一遍就把题刷到“完美”三数之和的去重、四数之和的剪枝这些细节第一次刷没写对太正常了。关键是每次复盘都要把错误写进自己的备注里而不是改个答案就完事。用我自己的进度来说三数之和我前后写过五遍但真正把去重逻辑内化成条件反射是从第二次独立重写开始的。坚持打卡的意义就在于反复接触这些套路直到某天拿到题面就能条件反射地说出“排序固定双指针”。最后再分享一个我这天刷完后的真实体会当天晚上我重新做了一遍昨天的两数之和试着用双指针去写发现需要先排序复杂度反而变成 O(n log n)没有哈希做法 O(n) 优雅。这一对比让我彻底意识到没有“万能的算法”只有“适不适合当前场景”的算法。哈希表的 O(1) 查询很香但它换不来顺序信息排序的双指针很优雅但它需要数据有序作为前提。能在不同题目里选对工具这才是刷题训练营真正想培养的能力。如果你的进度刚好在 Day6希望这篇复盘能帮你省下几个小时的踩坑时间。