代码随想录算法训练营刷到第六天，哈希表 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(m+n) |
| 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 不超过 200，O(n²) 完全可接受，这也是“空间换时间”的一个典型实例：把前一半的枚举结果存起来，后一半枚举时直接查表。
顺带提一个使用getOrDefault的注意点，很多语言里如果 key 不存在会返回 null 或 0，写不好可能抛异常或者漏加。Python 里推荐用get(key, 0)，Java 里推荐getOrDefault(key, 0)，一定要给默认值。
2.2 383 的字符计数：int[26] 为什么优于 HashMap
383 的题意翻译成人话就是：用 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[i+1]去跳过，就会误伤 left 指向 i+1 的情况。还是那个老例子[-1, -1, 2]，i=0、left=1 时正好组成合法答案，你跳到 i=1 就会发现 left=2，这个组合永远找不到了。
第二个原则是左指针去重，发生在记录答案之后：
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[i+1] + nums[i+2] > 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 的起始位置是i+1，所以去重条件要写成j > i+1，否则 j 第一次等于 i+1 时，比较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[i+1] + nums[i+2] + nums[i+3] > 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[j+1] + nums[j+2] > target，break。 - 如果
nums[i] + nums[j] + nums[n-2] + nums[n-1] < target，continue。
这两组剪枝的道理是一样的：先看“固定位置下能达到的最小四数和”和“最大四数和”，如果最小值都超了，后面不用看；如果最大值都不够，当前固定数可以直接换下一个。它们的作用不是改变复杂度量级，而是让常数小很多。实测数据中，这类剪枝能让耗时从几百毫秒降到几十毫秒，尤其在大数组上非常明显。
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[i+1]: continue | if i>0 and nums[i]==nums[i-1]: continue | 跳过 i 的同时会误伤 left=i+1 的组合 |
| 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，希望这篇复盘能帮你省下几个小时的踩坑时间。
