1. 哈希表part02在练什么：从查找效率看解题思路

代码随想录算法训练营走到第六天，哈希表part02这一天，可以说是我在整个哈希表章节里收获最大的一天。前一天的题还在练字母异位词、数组交集这类“验证哈希表能不能用”的热身动作，到了part02，题风直接变了：两数之和、四数相加II、赎金信、三数之和、四数之和，一层比一层烧脑，几乎把面试里哈希表和双指针的所有高频套路都过了一遍。今天这篇文章就把这几道题的核心思路、实现细节和我自己踩过的坑完整盘一遍，给同样在刷题或者准备面试的朋友做个参考。

先说说为什么哈希表值得拿出六天去练。哈希表的核心就一个词：查找。数组在知道下标时可以O(1)访问，哈希表则是把“值”通过哈希函数映射到“位置”，让你在不知道下标的情况下也能O(1)找到目标。直白点说，哈希表就是一本“字典”：你说一个词，我直接翻到那页，而不是从第一页开始逐页找。很多算法题卡人的点不是“怎么算”，而是“怎么找得快”，哈希表的价值恰恰就在这里。

1.1 为什么哈希表能“以空间换时间”

随便一个查找问题，最朴素的做法是线性扫描，一趟下来O(n)；如果你有一万个数据，最坏要扫一万次。哈希表走的是另一条路：先申请一块“足够宽”的存储区，再用哈希函数把数据散列到不同位置，查找时直接算出位置取出来，平均复杂度降到O(1)。

代价是什么？空间。同样的数据量，用数组或链表存储属于“刚好够用”，哈希表为了减少冲突通常要预留更多桶位，还要处理冲突链，内存占用往往高出一截。这就是典型的空间换时间。

还有个概念顺带说清楚：哈希表和字典的关系。很多语言里“字典”就是哈希表的一种实现，比如Python的dict、C++的unordered_map、Java的HashMap，底层原理都是先算哈希值、再定位桶。做题时没必要把它们想成两个东西，理解成同一个数据结构的不同叫法即可。

1.2 这一天的题单全景：四道题其实在考同一件事

part02的题单表面上是五道题，本质只考两件事：一类是用哈希表做配对查找，另一类是用双指针解决去重组合。我习惯把它们放在一起复盘，因为面试官常常会拿其中一题做引子，接着追问另一题的区别。

这五道题如果只看答案会觉得很散，但深入看会发现它们共享同一个思维起点：先分析暴力解法慢在哪里，再想能不能用“额外存储”或者“排序预处理”把关键步骤提速。明白了这个共性，刷题就轻松很多。

2. 两数之和与四数相加II：哈希表的“配对”思维

如果说哈希表part02有什么灵魂，那一定是“配对”两个字。两数之和是最朴素的配对，四数相加II是把配对提升到“两两配对”。这两题连着做，能非常直观地感受到哈希表如何把一个看似复杂的问题拆成简单查找。

2.1 两数之和：为什么必须“边查边存”而不是“先存后查”

题目本身很简单：给定数组nums和一个目标值target，找出和为target的两个数，返回它们的下标。天真的想法自然是双重循环，每个数都和后面的数加一遍，看看等不等于target，O(n²)当然能过小数据，但n到十万级别就歇菜了。

哈希表解法很多人听过：遍历数组，对每个nums[i]，去哈希表里查target - nums[i]有没有出现过。但有一个细节我见过无数人写错——到底该先把整个数组存进哈希表再查，还是遍历一边查一边存？

答案必须是边查边存。原因有两个。第一，如果先把所有元素存进去，遇到重复值比如nums = [3, 3]，target = 6，哈希表里键3对应的下标会被后一个3覆盖，查的时候很可能返回同一个元素的下标，或者直接查出一个错的下标。第二，假如数组中恰有一个元素的值等于target的一半，先存后查会把自己的值查出来，形成“一个数用了两次”的错误。

最稳的写法是这样的：

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> index; for (int i = 0; i < nums.size(); ++i) { int need = target - nums[i]; if (index.count(need)) { return {index[need], i}; } index[nums[i]] = i; } return {}; } };

每次先查补数，查不到才把当前值存进去，这样当遍历到第二个匹配元素时，哈希表里存的一定是另一个元素的下标，不可能出现自己匹配自己的情况。这个“先查后存”的顺序，是这题最容易踩的坑，也是面试官最喜欢追问的点。

2.2 四数相加II：把四层循环拆成两个两层循环

四数相加II是“两数之和”的加强版：给四个数组，每个数组选一个数，四个数加起来等于0，问有多少种组合。如果按题面直接写四层循环，复杂度O(n⁴)，n稍微大一点就直接告别AC。

这里需要意识到一件事：哈希表查询那么快，为什么不把四个数的组合拆成两组呢？先求A和B两个数组中所有两数之和，把每个和出现的频率存进哈希表；再遍历C和D两个数组的所有两数之和，去哈希表里查它的相反数出现过几次，把次数累加起来。

class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map<int, int> sumCnt; for (int a : nums1) { for (int b : nums2) { ++sumCnt[a + b]; } } int ans = 0; for (int c : nums3) { for (int d : nums4) { int need = -(c + d); if (sumCnt.count(need)) { ans += sumCnt[need]; } } } return ans; } };

很多新手在第二段里容易犯一个错误：查到need存在就ans++，而不是把频率sumCnt[need]累加上。要知道A和B里可能有多种组合都产生同一个和，比如a+b=7出现了3次，那么对于任何一组c+d=-7，都应该贡献3个答案，而不是1个。这是这题最容易漏的细节，也是“为什么哈希表要存频率而不是只存布尔值”的最好解释。

2.3 复杂度到底差多少：16亿次与4万次的区别

空谈复杂度不够直观，我用一个实际规模感受一下。假设每个数组长度n = 200，暴力四层循环要做200⁴ = 16亿次加法。常规在线评测系统一秒能跑大约几亿次简单操作，这已经接近极限甚至直接超时。而两两分组方案，前两层循环产生200² = 4万次，后两层又是4万次，总共8万次操作，加查表8万次，总数不到暴力解法的万分之一。

这就是“降维”的威力：同一个问题，把四个维度拆成两个维度分别处理，复杂度直接从O(n⁴)掉到O(n²)。顺着这个思路，如果题目变成“六数相加”，也可以考虑拆成三组两两配对，不过n稍大时内存会随之膨胀，需要评估空间承受能力，但配对分组这个思维模型是不会有错的。

3. 赎金信：用数组模拟哈希表的计数技巧

赎金信这道题相对简单，但它在训练营里出现的意义很特别：它告诉我们，哈希表并不一定非要开unordered_map，当数据范围小时，一个普通数组就能模拟出完美的哈希表，而且性能更快。

3.1 先看清题目本质：是“频度覆盖”而不是“字符在不在”

题目大意：给两个字符串ransomNote和magazine，判断ransomNote能不能由magazine里的字符构成，每个magazine字符只能用一次。很多人的第一反应是看ransomNote里的每个字符是不是都出现在magazine里，于是直接写“set包含判断”。

这个思路是错的。举个反例：ransomNote = "aa"，magazine = "a"，每个字符确实都出现在magazine里，但magazine只有一个'a'，根本不够用。所以这题的本质不是“字符存在不存在”，而是“magazine里每个字符的数量，够不够覆盖ransomNote的需求量”，也就是频度覆盖问题。

打个比方，食堂备菜，magazine是仓库里的食材库存，ransomNote是后厨下的订单，每样食材消耗一份，库存少了就出不了餐。判断依据永远是库存数量是否覆盖订单数量，而不是订单上的食材类别是否存在于仓库。

3.2 数组比unordered_map更快：26个字母不需要哈希函数

因为题目限制了字符串只包含小写字母，总共就26种可能，直接用数组开一个长度为26的计数器片段即可，不需要引入任何复杂结构。

class Solution { public: bool canConstruct(string ransomNote, string magazine) { int count[26] = {0}; for (char c : magazine) { ++count[c - 'a']; } for (char c : ransomNote) { if (--count[c - 'a'] < 0) { return false; } } return true; } };

为什么数组比unordered_map快？因为unordered_map要经过哈希函数计算桶位置，可能冲突还要走链表，动态扩容时甚至要重新散列所有元素；而数组版本的“哈希”就是一次字符减法c - 'a'，直接定位下标，没有任何冲突，没有扩容，常数极小。本质上我是在用数组手工实现一个“精确无冲突的哈希表”。

如果题目不再局限于小写字母，可以把数组扩大到128甚至256覆盖ASCII，或者直接用unordered_map<char, int>，思路完全一样，只是写法上要记得用键判断存在性，别因为find或count漏写导致误插入新键。

3.3 这个题最容易踩的两个坑

第一个坑是遍历顺序写反。必须先生成“库存”，也就是先遍历magazine累加数量，再遍历ransomNote消耗库存。如果反过来，或者两个字符串混在一起处理，很容易在遇到不存在的字符时直接把计数减成负数，导致误判。

第二个坑是使用unordered_map时直接写map[c]++，这个操作在键不存在时会自动插入一个值为0的新键，如果后续逻辑没处理好，垃圾键会越堆越多，内存变大不说，也会掩盖真正缺失的字符。用之前一定先判断键是否存在，或者用find、count这类查询接口先确认。

这道题虽然简单，但它把“哈希表的本质是计数统计”这个点讲得很透。贪快背代码没用，理解“频度覆盖”四个字，后面做很多字符串统计题都能直接用。

4. 三数之和与四数之和：为什么这两个题我放弃了哈希表

这一章可能是今天最有意思的部分。前面几题都是哈希表大显身手，到了三数之和、四数之和，我却建议大家放弃哈希表主方案，改用排序加双指针。别急着杠，先看完原因。

4.1 “和为零且不重复”让哈希表解法变得很别扭

三数之和题目是：在一个数组里找出所有不重复的三元组，三个数之和等于0。表面看还是配对查找，可以先固定一个数，再用两数之和的哈希表思路找另外两个数。但问题来了，题目要求“不重复的三元组”，数组里重复元素很多时，哈希表解法会产生大量重复结果。

为了去重，通常做法是先排序，固定前两个数后在哈希表里找第三个数，最后把所有结果放进一个set去重。这个方案能跑，但代码里到处是去重判断，一个地方写漏就出bug，而且额外set要占用不少空间。用这种方法做过这题的人都会觉得别扭：明明是个简单逻辑，怎么代码这么脏？

同样要排序，不如直接让双指针登场：排序之后，固定一个数i，用左指针指向i后面，右指针指向数组末尾，根据三数和与0的大小关系决定移动哪个指针。排序让“是否重复”变得非常好判断：相等的数字排在一起，跳过去就行。

4.2 双指针解法：排序是前提，去重是灵魂

先看完整代码，再讲几个关键点：

class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<vector<int>> res; int n = nums.size(); for (int i = 0; i < n - 2; ++i) { if (nums[i] > 0) break; // 剪枝：最小的都大于0，后面也不会更小 if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重a int left = i + 1, right = n - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { res.push_back({nums[i], nums[left], nums[right]}); while (left < right && nums[left] == nums[left + 1]) ++left; while (left < right && nums[right] == nums[right - 1]) --right; ++left; --right; } else if (sum < 0) { ++left; } else { --right; } } } return res; } };

去重这块，我重点说一个大家很容易写错的地方：外层i去重时为什么是nums[i] == nums[i - 1]，而不是nums[i] == nums[i + 1]？

因为我们要跳过的是“同一层循环下，起始值重复”的情况。nums[i] == nums[i + 1]这个判断会误伤合法的三元组。比如数组[-1, -1, 2]本身就是一组合法解，排序后第一个-1是i，第二个-1正好是left，如果写成nums[i] == nums[i + 1]就continue，直接把i=0这个合法位置跳过了，最后会漏解。所以外层去重一定记住“和前一个位置的元素比较”，这也是面试官最爱设的陷阱。

双指针内部同样需要去重：当发现一组和为零后，left和right先各自跳过所有重复值，再整体收缩。如果不跳过，外层i不变的情况下，left换到下一个重复值，right不变，又会组合出完全相同的三元组。

4.3 四数之和：剪枝容易写错的三个地方

四数之和相当于三数之和套了一层循环，代码框架一样，但有三个地方非常容易写崩，每个都是真金白银的教训。

第一，剪枝不能照搬三数之和的“nums[i] > 0就break”。因为四数之和的目标值target不一定是0，可能是负数。举个例子，target = -11，nums[i] = -5，-5比-11大，但后续三个数再取-5、-1、-1，加起来-12？需要验证能不能到-11，总之直接nums[i] > target就break是有问题的：当target为负，nums[i]大于target不代表凑不出更小的和。正确的剪枝是先看最小四数和：如果nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target，那后半部分只会更大，直接break；如果nums[i] + nums[n-1] + nums[n-2] + nums[n-3] < target，说明当前i太小，直接continue跳过。

class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); vector<vector<int>> res; int n = nums.size(); for (int i = 0; i < n - 3; ++i) { if ((long long)nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) break; if ((long long)nums[i] + nums[n-1] + nums[n-2] + nums[n-3] < target) continue; if (i > 0 && nums[i] == nums[i - 1]) continue; for (int j = i + 1; j < n - 2; ++j) { if ((long long)nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break; if ((long long)nums[i] + nums[j] + nums[n-1] + nums[n-2] < target) continue; if (j > i + 1 && nums[j] == nums[j - 1]) continue; int left = j + 1, right = n - 1; while (left < right) { long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right]; if (sum == target) { res.push_back({nums[i], nums[j], nums[left], nums[right]}); while (left < right && nums[left] == nums[left + 1]) ++left; while (left < right && nums[right] == nums[right - 1]) --right; ++left; --right; } else if (sum < target) { ++left; } else { --right; } } } } return res; } };

第二，四数之和的求和必须用long long。数组里四个int加起来可能溢出32位范围，尤其target可能是负数边界。我在测试时遇到过int溢出导致sum变成负数、指针乱移的诡异情况，后来统一转long long才稳。

第三，内层去重条件写成if (j > i + 1 && nums[j] == nums[j - 1]) continue，千万不能写成if (j > 0 && nums[j] == nums[j - 1])。因为j是从i+1开始的，如果i和j的值相等（比如数组里有两个-1，i取第一个-1，j取第二个-1），这是合法组合，不能用“j大于0就去重”误伤。经典场景是[-1, -1, 2, 5]，i=-1，j=-1，组合[-1,-1,5]是合法答案，不能跳过。

4.4 哈希表和双指针的适用边界总结

刷完这一组题，我给自己整理了一张“选型表”，现在也分享给你：

这个边界表比背十几行代码有用得多。面试时你第一时间判断出“这题该走哈希表还是双指针”，就已经赢了一半。

5. 常见问题与调试心得实录

写到这里，把这段时间刷题遇到的高频问题集中整理一下，尤其是我自己都踩过的坑，能帮你省下不少调试时间。

5.1 这几道题的高频报错与排查思路

还有一种很隐蔽的错误：sort排序后直接用原始题目的元素下标返回值，这种错在“两数之和”里出现率特别高，做了三数之和就容易串思路。每道题开写前先问一句自己“要不要返回下标”，能少写很多无用代码。

5.2 unordered_map和map选哪个：哈希表背后的效率常识

做题时经常纠结的问题：C++里到底用unordered_map还是map？两个都能当字典用，但底层完全不同。unordered_map底层是哈希表，查找平均O(1)；map底层是红黑树，查找O(log n)，而且插入要维护平衡，常数更大。大量查找和计数的场景，unordered_map优势非常明显。

但unordered_map不是没有缺点。它的key必须可哈希，像自定义struct要自己提供哈希函数；迭代顺序不确定，今天遍历出的顺序可能是乱的，如果题目要求有序输出，别自找麻烦，直接map。另外哈希表扩容时会一次性搬运数据，极端情况下某次操作可能突然变慢，但做题时基本不会感受到，不用过度担心。

Python用户则不用纠结：dict和set底层就是哈希表，直接用就行。要注意的是Python整数哈希没有哈希冲突问题，性能一般很稳定。

5.3 训练营阶段的复习节奏与做题顺序建议

我建议按这个顺序去做今天的题单：赎金信、两数之和、四数相加II、三数之和、四数之和。理由很简单，由浅入深。赎金信建立“计数思维”，两数之和建立“补数思维”，四数相加II建立“分组降维思维”，三数之和建立“去重思维”，四数之和综合所有思维并加入剪枝细节。

复习节奏上，我做了一个自认为效果很好的安排：当天晚上不看答案，把四数之和完整重写一遍；第二天早晨把两数之和、四数相加II默写一遍；一周后再把三数之和和四数之和各写一次。这个节奏看起来重复，但特别有效，尤其是双指针去重逻辑，不重写几遍真的会忘。我见过太多人只是看懂了题解就觉得自己会了，结果面试一紧张，去重条件写成了nums[i] == nums[i + 1]，直接送命。

还有个经验是建立错题笔记，不要只记“我超时了”，而是记录“为什么超时”“换成什么思路解决”“这类题的标志是什么”。比如看到“返回下标”就想起哈希表，看到“不重复组合”就想起排序双指针。长期积累下来，每道题在你心里都会有一个触发标记，刷题速度和准确率都会明显提升。

最后说两句心里话。第六天结束之后我最大的体会是，哈希表真正值钱的不是“用map查了一下”，而是它教你换一个角度看待问题：两数之和是把查找变成补数，四数相加II是把组合变成分组频率，赎金信是把判断变成计数。这几个思维模型比代码本身有用得多。

另外一个小技巧是：凡是拿到一道题，先别急着写代码，先花几十秒把暴力解法的复杂度写在草稿纸上。四数相加暴力是O(n⁴)，你会瞬间明白必须拆；三数之和暴力和哈希表去重都麻烦，你会判断双指针更合适。这个习惯我在后面很多题里都受益，强烈推荐你也试试。