1. 哈希表part2三道题练完是什么感觉把“代码随想录”刷到第7天今天的主题是哈希表part2。如果你跟我一样是从第6天连续刷过来的应该已经接触过哈希表的基础用法用数组模拟简单的字符哈希表用set去重或判断存在性。但说实话那几道题只是入门真正把哈希表的威力发挥出来靠的是map的应用。Day 07排了三个题两数之和LeetCode 1、赎金信LeetCode 383、四数相加IILeetCode 454。三个题都是哈希表的经典场景但应用方式完全不同。两数之和是“边遍历边查表”考察一次遍历内如何利用已有的数据赎金信是“用数组模拟哈希表做频次统计”考察对哈希表底层实现的掌握四数相加II则是“分组统计、降维打击”考察如何把高复杂度问题拆成低复杂度的子问题。同样的数据结构三种完全不同的解题哲学。这篇文章适合两类人一是想跟着复习、对照思路的算法初学者二是准备面试想快速把哈希表题型重新过一遍的人。我不会只贴代码我会把为什么这么想、踩过哪些坑、面试会怎么追问都写出来这种“过程感”是最容易被忽略但最有价值的部分。先声明一下刷题前看数据范围非常重要后面每一道题我都会先说清楚数据规模因为很多解法的判断依据就是数据量。2. 两数之和一次遍历加map查表2.1 题目与初步尝试LeetCode 1题给定一个整数数组nums和一个整数target返回两个数的下标使得这两个数的和等于target。输入保证有且仅有一组答案而且同一个元素不能重复使用。我第一次看到这题时第一反应就是暴力。两个for循环外层i从0到n-1内层j从i1到n-1判断nums[i] nums[j] target找到就返回。当时我觉得挺好时间复杂度O(n²)空间O(1)思路清晰代码也短。后来我把代码丢到LeetCode上去跑发现数据量大的时候运行时间很难看。如果数组长度一万复杂度就是一亿次比较勉强能过如果长度十万那就是更庞大的比较次数直接超时。所以我的建议是先把暴力解写出来用来验证思路和引出差值然后再想更优解法把它当成对照实验非常方便。2.2 为什么哈希表能把查找降下来暴力解法慢在哪慢在“找补数”这个动作。拿到nums[i]我要到后面的区间里线性查找target - nums[i]这个查找是O(n)的。如果能把“找”这个动作变成O(1)那整个算法就变成了O(n)。哈希表干的就是这件事。它的本质是一个映射结构key是值value是这个值的下标。当我遍历到第i个数时我就在哈希表里问target - nums[i]在不在如果在答案立刻出现如果不在我把nums[i]和下标i塞进表里继续往后走。这个过程可以类比成你在教室里找某个人。暴力法是这样从头到尾挨个问“你是张三吗你是张三吗”问到最后才找到。哈希表是这样每进教室就登记一个“我坐在第几排我叫什么”以后要找张三直接看登记表不用挨个问。空间换时间就是它的代价。2.3 用map而不是set为什么这里有个初学者经常犯的错误以为这题用set就行因为判断“补数是否存在”只需要一个集合。但题目要求返回下标set只存值不存下标你找到补数后不知道它在哪。所以这道题必须用map存值到下标的映射。如果你问“那我不返回下标只返回存在与否呢”那set就够用了。但更常见的变体是返回下标所以这道题的标准解法就是unordered_map。这个点面试官经常追问你最好能答出set和map在“存储信息量”上的差别。2.4 完整代码和两个需要注意的地方C版本class Solution { public: vectorint twoSum(vectorint nums, int target) { unordered_mapint, int mp; for (int i 0; i nums.size(); i) { int complement target - nums[i]; if (mp.count(complement)) { return {mp[complement], i}; } mp[nums[i]] i; } return {}; } };Python版本class Solution: def twoSum(self, nums: List[int], target: int) - List[int]: seen {} for i, num in enumerate(nums): complement target - num if complement in seen: return [seen[complement], i] seen[num] i return []我在面试时被问过两次“这个代码有什么隐藏的问题”答案其实都在“先查后存”的顺序。如果数组是[3, 2, 4]target是6你见到3应该先问“补数3在不在”不在然后存3。如果先存再查查到3自己返回[0,0]同一个元素就被用了两次这违背题意。顺序写反就是错解。第二个注意点是当数组里出现重复元素时map里只会保存最后一次的下标。题目保证唯一解不会出现两个相同元素都能组成答案的情况所以这步没问题。万一题面改成“可能有多个答案随便返回一个”代码依然能跑如果改成“返回所有配对”那就不能只存一个下标了需要存一个列表。C里我习惯用count或者find判断键是否存在避免直接使用operator[]因为它有一个副作用当键不存在时会插入一个默认值。这个副作用虽然不影响本体的逻辑但会污染哈希表也可能拖慢后续操作。2.5 复杂度到底怎么描述两数之和的时间复杂度是O(n)因为只遍历一次每次哈希表的查找和插入平均O(1)。最坏情况下如果哈希函数设计不好一个桶里挂了一堆元素查找退化成O(n)那总体是O(n²)。但实际工程里用unordered_map基本不会出现这种情况平均性能很稳所以描述为O(n)即可。空间复杂度是O(n)因为最多存n组键值对。面试时最好把这个也说出来说明你考虑过资源的消耗。很多人只记得“快”忘了提空间这在要求严格的面试里会被视为考虑不周全。3. 赎金信数组就是最简单的哈希表3.1 问题描述与数据范围LeetCode 383题给定两个字符串ransomNote和magazine判断ransomNote能不能由magazine里面的字符构成。每个字母在magazine中只能使用一次。比如magazineaabransomNoteab可以ransomNoteaaab不可以因为a只有两个。通常的输入约束是字符串由英文小写字母组成。这就是关键信息。小写字母一共26个哪怕magazine长度是10万它的字符也只有26种可能。3.2 为什么这里最适合用数组模拟哈希表用map虽然也行但有两点不合适第一map的底层实现如果是红黑树插入、查找都是log n级别第二map在遇到Key不存在时会插入默认值处理计数的时候容易出bug。而且这里键的取值范围是已知且固定的26个小写字母完全可以用数组来模拟哈希表下标就是字符的编号值就是出现次数。这种用数组当哈希表其实反映了哈希表最古老也最简单的实现方式——直接寻址。优点是快O(1)时间就能完成查找和修改缺点是只能应对键值范围有限的场景。在这个题目里26个键正好是这个场景。3.3 完整解法思路第一步遍历magazine用一个长度为26的数组cnt统计每个字母出现几次。 第二步遍历ransomNote每遇到一个字母就把它在cnt中对应的计数减一。如果某个字母的计数变成负数说明magazine提供的该字符不够用直接返回false。 第三步如果整个ransomNote都遍历完没有负数返回true。代码class Solution { public: bool canConstruct(string ransomNote, string magazine) { int cnt[26] {0}; for (char c : magazine) { cnt[c - a]; } for (char c : ransomNote) { cnt[c - a]--; if (cnt[c - a] 0) { return false; } } return true; } };时间复杂度O(nm)n是magazine长度m是ransomNote长度。空间O(1)因为数组长度永远是26不随输入增长而增长。这个空间复杂度必须写对有些人会说O(n)那是错的数组是固定大小不占用的比例不会扩大。3.4 跟上一part的“有效字母异位词”对比在代码随想录day06你大概率做过242题“有效的字母异位词”。那道题的本质是判断两个字符串的字母频次是否完全一样。实现方式同样是统计字母频次但最后一步是比较只有每个字母频次都相等才算异位词。383题是242题的弱化版——不要求相等而是要求ransomNote的每个字母频次小于等于magazine的对应频次。也就是说242题的“相等判断”换成“不小于判断”就能得到383的解法。这个对比特别有价值因为它告诉你哈希表频次统计题的基本框架是一样的变的只是查询的约束条件。如果面试官问你这两个题的区别你可以说242判断两个字符串是否互为排列要求频次完全相等383判断一个字符串能否由另一个字符串组成不关心字符出现顺序只要求所有频次不超过原材料即可。本质是同一个计数模型下的两个不同约束。3.5 实操中容易被忽略的细节第一个细节题目中字符串长度可能很大如果ransomNote长度大于magazine直接返回false这行特判能让你的代码在极端情况下更快也让面试官觉得你考虑过空数据和极端数据。第二个细节如果题目改成包含大写字母数组长度就要从26变成52如果包含数字那可能要变成62或128。边界扩展是这类数组哈希表题目的经典追问你要能举一反三说出“遇到多字符集就把数组长度改成128或256即可”。第三个细节C里用字符减a来计算下标这个技巧看起来很琐碎但每次都要想清楚。如果字符串里包含非小写字符比如空格那你用26就会越界。所以看清楚题目的范围约束比什么都重要。4. 四数相加II降维打击从O(n⁴)到O(n²)4.1 题目与初步感受LeetCode 454题给四个长度都为n的整数数组nums1、nums2、nums3、nums4统计所有满足nums1[i] nums2[j] nums3[k] nums4[l] 0的四元组(i, j, k, l)的数量。这道题第一次见脑子里的直觉是暴力。四个数组每个遍历一遍四重循环复杂度就是O(n⁴)。如果n是200四重循环就是16亿次操作明显超时。如果n是500那更是天文数字。所以必须优化。4.2 分组为什么能降维数学上的关键等式a b c d 0 等价于 a b -(c d)。所以我先枚举前两个数组的所有组合把每种和的值及其出现次数记录在map里。然后再枚举后两个数组的所有组合对每一种和我去map里查找它的相反数把次数累加进答案。打个比方你要找人匹配四条线索如果四条线索一起找复杂度是指数级。但你先从前两条线索的组合中建立一张“需求表”再用后两条线索去查这张表问题就变成了两个小问题。这就是分组。这个解法的时间复杂度是O(n²)O(n²)O(n²)空间O(n²)。因为第一个map最多有n²种不同的组合和当n是200时n²只有4万完全没问题。4.3 写代码以及那些坑我写出标准解法前先说一个容易踩的坑很多人会把前两个数组的组合存入map然后再遍历后两个数组直接用m[-(cd)]取值这样一行就能累加答案。但在C里m[key]如果key不存在会自动生成一个值为0的键值对插入。在四数相加II这题这不是致命错误但如果map的键变得很大大量不存在的键会被创建进而触发rehash拖慢性能。更稳妥的方法是先find存在再累加。class Solution { public: int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) { unordered_mapint, int mp; for (int a : nums1) { for (int b : nums2) { mp[a b]; } } int ans 0; for (int c : nums3) { for (int d : nums4) { int target -(c d); auto it mp.find(target); if (it ! mp.end()) { ans it-second; } } } return ans; } };这个代码不复杂但有几个点值得注意。第一mp[ab]这种写法能正确处理空值因为operator[]会先返回0再加1。这是map计数最常用的写法也最容易理解。第二负数和零没影响。如果nums里有负数ab可能是负的map的key照样能处理。零的相反数还是零统计起来也自然。第三答案可能超出int范围。如果四个数组长度都是1000组合数是10¹²级别即使答案数量远小于组合数仍可能很大。刷题时看数据范围如果不放心就定义成long longPython则不用考虑这个。4.4 为什么说它与两数之和是同一类题如果把这题拆开来看后半部分的“遍历后两个数组在map中查找-(cd)”本质上就是一个两数之和问题——只不过这里的“target”是-(cd)而查找表是之前构建的map。所以某种程度上四数相加II是两数之和的推广把两个数之和去查另一个和变成把四个数分成两组分别问“两组之和相加为零的可能性数量”。这个思路可以继续推广如果给六个数组要求六数之和为零同样可以用分组策略33分组复杂度从O(n⁶)降到O(n³)。当然实际题目很少这样出但这个推广思维在讨论最优解法时很有用。4.5 另一类解法两两分组加排序该怎么分析有些人会问能不能把前两个数组的和存成vector再排序然后遍历后两个数组组合用二分查找计算有几个等于目标值可以但时间复杂度变成O(n² log n)比哈希表的O(n²)慢一个log因子。面试时如果有人提出这个方案你可以分析为什么二分加排序不如哈希表。当然也要能说出哈希表最坏情况下可能退化成O(n²)的风险。讨论这种trade-off比背下标准答案更能体现算法功底。我自己更倾向于把两种解法都写下来然后对着数据范围做选择而不是一上来就背答案。5. 三道题串起来看哈希表用法其实分三类5.1 查表、计数、分组三个核心场景把day06和day07加起来哈希表题目大概分三类。第一类是判重和存在性问题。典型是两数之和里的“判断补数是否存在”还有day06的“两个数组的交集”。这类题用set或map重点是理解“存在性”和“位置、次数”的区别。第二类是频次统计问题。典型是赎金信和有效的字母异位词。核心是“key是字符value是次数”实现可以是数组、map取决于字符串的字符集范围。第三类是分组累加问题。典型是四数相加II。核心是把问题拆成两个子集合用map记录映射再查询。这个思路还会在后来的三数之和、四数之和里变形出现。从这一角度看你不再需要死记硬背每道题的代码而是要知道每道题属于哪种模型再套模型分析。这个意识比多刷十道题有用。5.2 为什么说哈希表本身不复杂场景才是难点哈希表本身只是一个结构真正难的是识别出它应用在哪个环节。你在两数之和里用map存下标在赎金信里用数组统计频次在四数相加II里用map存储组合和次数。同一个数据结构用法差别很大。面试官想看的就是你能不能快速判断一个场景应不应该用哈希表、用哪种哈希表。我自己的判断方法是拿到题先问我要频繁查找什么查找的对象有什么特征如果查找的目标是某个值是否存在、出现多少次、在哪个位置那哈希表大概率能帮上忙。如果目标是有序遍历、范围查询那用排序或树结构更合适。这个习惯能让你少走很多弯路。5.3 数组、set、map用一张表记住选择题答案场景用什么结构原因键范围固定且很小比如26个字母数组最快O(1)无哈希额外开销只判断存在性不记录附属信息set最小化存储记录存在性加下标、次数mapset存放不下附属信息键范围巨大且不固定map数组会浪费空间或越界这张表是我刷题后自己总结的不一定适用于所有题目但覆盖了绝大多数情况。面试时如果题目要求“返回一个布尔值”而你用了map会被追问为什么不用set如果用了数组而题目字符范围很大会被追问数组会不会越界。所以选结构前先说清楚约束条件别等被问的时候才解释。6. 哈希表刷题中容易翻车的地方6.1 map的operator[]副作用C里map的operator[]在key不存在时会创建默认值这是好事也是坑。好处是写计数时方便比如mp[ab]就能直接统计坑是当你只是想查询而不想插入时它会污染哈希表的内容。前面两数之和、四数相加II我都提到这点。建议把“用find或count查询”养成肌肉记忆面试时就不容易出意外。6.2 哈希冲突导致的极端性能问题从原理上说如果哈希函数设计不合理或者输入被故意构造让所有元素都映射到同一个桶哈希表的最坏性能会退化成O(n)。LeetCode偶尔会卡某些哈希算法比如有人用Python的set或map时会遇到构造的碰撞用例。想让代码更稳有时候可以考虑自定义哈希结构或者干脆用数组做哈希表来规避。这个点不用深究但面试官问“哈希表从性能上什么时候会出错”时你要能答出来最坏情况是很多元素被映射到同一个桶退化成链表式的线性查找。6.3 数组越界和不统一的数据类型赎金信那道题如果你只开26个int万一题目包含大写字母索引就可能越界。解决方法是先确认字符的取值范围或者用一个足够大的固定数组比如256。刷题时看到“由小写字母组成”的描述一定要读到关键字再动手。四数相加II里也要注意结果类型C里如果数组长度到几千答案用int可能不够直接用long long保险。6.4 边界测试用例怎么构造我把压箱底的一套测试用例分享给你。哈希表题目写完以后至少自己跑过这几个case空字符串、空数组只有一个元素的数组所有值都相等的数组负数和零的组合最大数值的溢出可能性对两数之和来说测一个[3,2,4], target6看是不是返回[1,2]而不是[0,0]。对四数相加II来说测全零数组看答案是否符合预期。这些细节能帮你提前规避很多低级错误面试时也能显得更稳重。整组题刷下来我最大的感受是哈希表的作用不是算法有多高级而是让“查询”变得便宜。一旦查询便宜了很多原本要暴力查找的题目就能直接降维度。两数之和用查询替换顺序查找四数相加II用查询替换和式枚举赎金信用计数表替换逐字符匹配。问题变了思路其实没变。Day 07的三道题全都属于哈希表的“舒适区”但如果你只看题解很容易看完就忘。我的建议很朴素每道题做完先合上题解自己复现一遍再试试变体比如把两数之和改成“返回所有可能组合”把四数相加II改成“返回具体下标”。这些变体才是真正帮你掌握思路的钥匙。下一篇是哈希表part3难度会明显上来主要是三数之和和四数之和的双指针解法跟今天的分组思想有点关联顺着这条线索往下刷会比较顺。