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的题单表面上是五道题本质只考两件事一类是用哈希表做配对查找另一类是用双指针解决去重组合。我习惯把它们放在一起复盘因为面试官常常会拿其中一题做引子接着追问另一题的区别。题目核心考察点推荐数据结构时间复杂度两数之和补数查找、返回原始下标unordered_mapO(n)四数相加II分组降维、频率统计unordered_mapO(n²)赎金信字符频度覆盖、数组模拟哈希int[26]O(n m)三数之和排序、去重、双指针排序后的数组O(n²)四数之和三数之和扩展、多种剪枝排序后的数组O(n³)这五道题如果只看答案会觉得很散但深入看会发现它们共享同一个思维起点先分析暴力解法慢在哪里再想能不能用“额外存储”或者“排序预处理”把关键步骤提速。明白了这个共性刷题就轻松很多。2. 两数之和与四数相加II哈希表的“配对”思维如果说哈希表part02有什么灵魂那一定是“配对”两个字。两数之和是最朴素的配对四数相加II是把配对提升到“两两配对”。这两题连着做能非常直观地感受到哈希表如何把一个看似复杂的问题拆成简单查找。2.1 两数之和为什么必须“边查边存”而不是“先存后查”题目本身很简单给定数组nums和一个目标值target找出和为target的两个数返回它们的下标。天真的想法自然是双重循环每个数都和后面的数加一遍看看等不等于targetO(n²)当然能过小数据但n到十万级别就歇菜了。哈希表解法很多人听过遍历数组对每个nums[i]去哈希表里查target - nums[i]有没有出现过。但有一个细节我见过无数人写错——到底该先把整个数组存进哈希表再查还是遍历一边查一边存答案必须是边查边存。原因有两个。第一如果先把所有元素存进去遇到重复值比如nums [3, 3]target 6哈希表里键3对应的下标会被后一个3覆盖查的时候很可能返回同一个元素的下标或者直接查出一个错的下标。第二假如数组中恰有一个元素的值等于target的一半先存后查会把自己的值查出来形成“一个数用了两次”的错误。最稳的写法是这样的class Solution { public: vectorint twoSum(vectorint nums, int target) { unordered_mapint, 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(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) { unordered_mapint, 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里可能有多种组合都产生同一个和比如ab7出现了3次那么对于任何一组cd-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 aamagazine 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_mapchar, 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: vectorvectorint threeSum(vectorint nums) { sort(nums.begin(), nums.end()); vectorvectorint 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直接把i0这个合法位置跳过了最后会漏解。所以外层去重一定记住“和前一个位置的元素比较”这也是面试官最爱设的陷阱。双指针内部同样需要去重当发现一组和为零后left和right先各自跳过所有重复值再整体收缩。如果不跳过外层i不变的情况下left换到下一个重复值right不变又会组合出完全相同的三元组。4.3 四数之和剪枝容易写错的三个地方四数之和相当于三数之和套了一层循环代码框架一样但有三个地方非常容易写崩每个都是真金白银的教训。第一剪枝不能照搬三数之和的“nums[i] 0就break”。因为四数之和的目标值target不一定是0可能是负数。举个例子target -11nums[i] -5-5比-11大但后续三个数再取-5、-1、-1加起来-12需要验证能不能到-11总之直接nums[i] target就break是有问题的当target为负nums[i]大于target不代表凑不出更小的和。正确的剪枝是先看最小四数和如果nums[i] nums[i1] nums[i2] nums[i3] target那后半部分只会更大直接break如果nums[i] nums[n-1] nums[n-2] nums[n-3] target说明当前i太小直接continue跳过。class Solution { public: vectorvectorint fourSum(vectorint nums, int target) { sort(nums.begin(), nums.end()); vectorvectorint res; int n nums.size(); for (int i 0; i n - 3; i) { if ((long long)nums[i] nums[i1] nums[i2] nums[i3] 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[j1] nums[j2] 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是从i1开始的如果i和j的值相等比如数组里有两个-1i取第一个-1j取第二个-1这是合法组合不能用“j大于0就去重”误伤。经典场景是[-1, -1, 2, 5]i-1j-1组合[-1,-1,5]是合法答案不能跳过。4.4 哈希表和双指针的适用边界总结刷完这一组题我给自己整理了一张“选型表”现在也分享给你问题特征推荐方案原因需要返回原始下标哈希表排序会破坏下标信息只需要统计配对数量不要求列出组合哈希表计数组合数量可以用频率累加字符范围小且固定数组模拟哈希常数小、无冲突、写起来快要求列出所有不重复的组合且允许排序排序 双指针去重逻辑直观、空间O(1)目标和target可能是负数双指针时要小心剪枝不能简单和target比大小这个边界表比背十几行代码有用得多。面试时你第一时间判断出“这题该走哈希表还是双指针”就已经赢了一半。5. 常见问题与调试心得实录写到这里把这段时间刷题遇到的高频问题集中整理一下尤其是我自己都踩过的坑能帮你省下不少调试时间。5.1 这几道题的高频报错与排查思路典型报错/现象可能原因解决办法两数之和返回两个相同下标先全部存表再查询自己匹配自己改成边查边存四数相加II结果数量偏少命中哈希表后只res没加上频率值使用res sumCnt[need]赎金信把小写字母范围当大字符集处理误用unordered_map忘记存在性判断优先用count[26]三数之和出现重复三元组外层i去重没写或去重比较对象写错i与i-1比较不是与i1比较三数之和left/right指针死循环找到结果后没跳过重复值也没收缩指针while去重后left、right--各执行一次四数之和剪枝直接RE或超时剪枝条件比较错误或int溢出用long long比较最小四数和与最大四数和还有一种很隐蔽的错误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⁴)你会瞬间明白必须拆三数之和暴力和哈希表去重都麻烦你会判断双指针更合适。这个习惯我在后面很多题里都受益强烈推荐你也试试。