哈希表这块到Part02基本就是硬仗了。Day7的内容放在整个算法训练营的节奏里看恰好是从“会用哈希表”过渡到“会选哈希表”的分水岭。前面Part01大家已经熟悉了数组、set、map的基本操作但真正在LeetCode上做题你会发现哈希表单独出现的概率其实没那么高更多时候它是和双指针、排序、模拟这些手段混在一起用的。这一天的四道题——四数相加、赎金信、三数之和、四数之和恰好把“哈希表与其他解法如何取舍”这件事讲透了。1. 先聊清楚这一天题目背后的设计逻辑1.1 为什么Part02选的偏偏是这四道题很多人刷题有个误区觉得题目难度越高越值得做。但实际上训练营安排的题目往往有非常明确的教学意图。Day7的四道题按顺序是四数相加II454题赎金信383题三数之和15题四数之和18题这个顺序不是随便排的。四数相加是第一道“哈希表思路能直接秒杀”的题而且它涉及一个非常重要的思想分组降维。赎金信看起来简单但它考察的是“哈希表什么时候优于其他解法”的判断力属于典型的易错题。三数之和和四数之和则是重头戏因为你会发现最优解压根不用哈希表反而用双指针。把这几道题放在一起核心目的就是让你建立一种“先分析再定解法”的习惯而不是看到“求和”就条件反射地往上套哈希表。1.2 哈希表和双指针在这个阶段的优先级我得先把结论放在前面三数之和、四数之和这两道题训练营的标准要求是必须掌握双指针解法哈希表解法可以作为拓展了解。为什么因为哈希表在“去重”这件事上非常痛苦你去重需要大量额外的判断逻辑代码很容易写成一堆if堆叠面试或笔试时也会显得思路混乱。双指针配合排序去重逻辑会清爽很多。但四数相加II这道题不一样它明确适合用哈希表因为它的四个数组是独立的不需要考虑去重问题。哈希表的优势在于“快速定位是否存在以及出现了多少次”凡是能拆成“两组两两配对”的场景它都特别合适。所以我一直跟学员说刷题最重要不是背模板而是搞清楚每道题最适合的几种解法到底是什么以及为什么是它们。2. 四道题的核心思路与实操拆解2.1 四数相加II哈希表的教科书式用法这道题背景很简单给你四个长度相同的整数数组从每个数组里各取一个数有多少种组合能让四个数相加等于0。暴力解法是四层循环复杂度O(n^4)遇到几百长度的数组直接算到天荒地老。核心思路是分组。把四个数组分成两组A和B一组C和D一组。先遍历A和B把所有两数之和放入一个哈希表key是“和的值”value是“这个和出现的次数”。再遍历C和D计算它们的和的相反数去哈希表里查这个相反数是否存在如果存在就把对应的次数累加到结果里。def fourSumCount(A, B, C, D): count_map {} for a in A: for b in B: s a b count_map[s] count_map.get(s, 0) 1 result 0 for c in C: for d in D: target -(c d) if target in count_map: result count_map[target] return result这个写法的时间复杂度是O(n^2)空间复杂度也是O(n^2)。为什么它比直接四层循环快因为两两分组之后我们只用遍历两次两两组合也就是2倍的n^2而不是n^4。用一个生活化的类比你要从四副牌里各抽一张凑出某个点数如果一上来就抽四张组合数量是天文数字但如果先把前两副牌的所有组合点数登记在册再拿后两副牌的组合去对账瞬间就把问题缩小到了一个可以接受的范围。实操中有几个细节我必须强调字典的get方法比if key in dict再取值的写法更简洁但不代表那个写法就错。建议新手先把逻辑理清再用get简化。这道题不关心组合的具体元素是什么只关心组合的数量所以value存次数就足够了。很多同学一开始会自然想存“组合的下标组合”但在这里完全不需要。数据范围允许数字和结果为负数所以哈希表的key可以是负数不用做偏移处理。2.2 赎金信什么时候该用哈希表什么时候数组更香赎金信这道题题意是你有一本杂志字符串和一个赎金信字符串问赎金信能不能由杂志里的字符拼出来每个字符只能用一次。刷题经验少的人看到“字符出现次数”第一反应就是建哈希表。但仔细想想这里的字符集范围是什么题目限定是小写英文字母也就26个。对于这种“元素范围非常有限且已知固定”的场景用数组当哈希表才是最优解。数组的下标天然就是字符的映射只需要把字符的ASCII码减去‘a’的值作为下标就能实现O(1)的存取而且完全不需要处理哈希冲突速度更快内存消耗也更稳定。def canConstruct(ransomNote, magazine): record [0] * 26 for ch in magazine: record[ord(ch) - ord(a)] 1 for ch in ransomNote: index ord(ch) - ord(a) if record[index] 0: return False record[index] - 1 return True这道题我觉得真正值得学的不是解法本身而是**“数据范围决定数据结构”**这个思维。哈希表字典是什么时候都用得上的万能工具箱但万能不代表最优。当你看到“小写字母”“26个字母”“0到100之间的整数”这类限定词就应该立刻想到数组。反之如果字符集很大、不确定或者key的类型是字符串、元组这种复合结构再用真正的哈希表。实操中容易踩的坑忘记先遍历杂志再遍历赎金信顺序反了会导致误判。只统计了杂志里每个字符是否有而没统计足够数量。比如杂志有两个‘a’赎金信要三个‘a’如果只存布尔值就会出错。直接用Python的Counter后用减法判断剩余值是否为负数这种思路也可以但底层原理仍然是哈希表。我自己更喜欢数组版因为它连哈希碰撞的担忧都没有。2.3 三数之和双指针才是正解哈希表为何反成累赘三数之和是这一天的核心难点。题目要求给你一个整数数组找出所有不重复的三元组使得三元组的和为0。注意“不重复”三个字这是整道题最折磨人的地方。先看哈希表的思路固定一个数然后对剩下的两个数用类似两数之和的方法去哈希表中查找。但问题来了查到的结果里可能包含同一个元素用了两次的情况也需要处理重复元素导致的三元组重复问题。最后的去重逻辑非常恶心可能要同时维护多个set代码长度暴涨而且极其容易漏掉边界条件。双指针解法就清爽得多。第一步先排序然后固定一个指针i从左往右遍历作为三元组第一个数。接着在i右侧区间用left和right两个指针相向而行找两个数与nums[i]的和为0。每找到一个合法三元组就移动指针并且跳过所有重复值。def threeSum(nums): nums.sort() result [] n len(nums) for i in range(n): if nums[i] 0: break if i 0 and nums[i] nums[i - 1]: continue left i 1 right n - 1 while left right: total nums[i] nums[left] nums[right] if total 0: right - 1 elif total 0: left 1 else: result.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 result为什么排序以后就简单了因为有序数组天然具备了“大了往左缩小了往右扩”的能力。三个数的和如果大于0说明右边的数太大了要右指针左移小于0说明左边的数太小了要左指针右移。这个过程本质上是在有序空间里做二分式逼近逻辑清晰去重也容易——只要保证同一个数值只被当作同一位置元素用一次就行。去重的核心有两条外层循环i去重时必须用nums[i] nums[i - 1]判断而不是nums[i] nums[i 1]。因为后者会跳过i本身作为三元组起点的可能性。我见过太多人在这里写反导致结果缺失。找到一组结果后left和right各自跳过重复值时跳完还要再各自移动一步否则会陷入死循环。很多人写完跳过逻辑忘了最后那两行left 1和right - 1然后对着超时报错发懵。这道题用双指针的复杂度是O(n^2)排序的O(n log n)可以忽略不计。哈希表做法的复杂度也是O(n^2)但常数项大得多而且去重极其费劲。所以训练营里我强烈建议大家至少把双指针版本背下来面试里能写对比写得“别出心裁”重要得多。2.4 四数之和双指针法的进阶变形与其他关键取舍四数之和可以看作三数之和的套娃版。核心思路是在三数之和的外面再套一层循环先固定两个数剩下的区间仍然用双指针去逼近。def fourSum(nums, target): nums.sort() result [] n len(nums) for i in range(n): if i 0 and nums[i] nums[i - 1]: continue for j in range(i 1, n): if j i 1 and nums[j] nums[j - 1]: continue left j 1 right 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: result.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 result这里有一个非常关键的细节是很多讲解会一带而过的这里去重为什么用nums[i] nums[i - 1]而不是nums[i] nums[i 1]原理和前面三数之和完全一样。你固定的是当前这一层循环的起点如果和上一个已经处理过的数相同说明从它开始的所有组合在前一轮已经枚举过了跳过它才能避免重复。而如果去比较nums[i]和nums[i 1]会直接误伤因为i 1位置在今后的遍历中还有机会作为“当前层起点”被合法使用。四数之和还有个额外需要注意的点target不再是0可能是任意整数所以剪枝条件不能写死成nums[i] target就break。比如全是负数且target是负数的时候第一个数大于target但仍然可能有解。解决方法是只有在target为正的前提下才做这种提前终止或者干脆不做剪枝直接完整遍历。面试时为了减少出错我个人的习惯是只在确定条件安全时加剪枝拿不准就先不加。从复杂度看四数之和是O(n^3)这也是双指针法能到达的上限了。如果n是几百还勉强能扛几千以上就会很吃力但那种规模通常会有其他专门解法面试不常考。2.5 对比总结三道求和题三种不同的解法倾向把这三道题放在一起看会特别有意思。四数相加II用哈希表轻松解决三数之和用双指针最优四数之和是三数之和的扩展版。它们看起来都是“几个数相加等于某个值”但内部逻辑完全不同。原因是什么关键在于“多个数组还是单一数组”以及“要不要去重”。多个独立数组每组内部取一个数适合分组哈希表因为不需要考虑索引互斥问题。单一数组内部选几个数天然存在“同一元素不能用两次”的限制还有“三元组/四元组不能重复”的约束这时哈希表的快速查找优势就被去重成本抵消了。双指针法必须建立在有序数组之上如果题目不允许排序比如要求保持原数组顺序那就得另想办法。但这三道题里不存在这个限制。建议把这四道题的解法倾向整理成一张表放在自己的刷题笔记里题目推荐解法核心复杂度去重难度四数相加II分组哈希表O(n^2)低无需去重赎金信数组计数O(n)低三数之和排序双指针O(n^2)中需仔细处理四数之和排序双指针O(n^3)中多层去重3. 完整实操流程从读题到AC的关键细节实录3.1 什么时候该先排序什么时候绝不能排序刷完这几道题一个很自然的疑问是我拿到一道题怎么判断能不能排序我的经验是只要题目允许改变数组本身顺序并且不用返回原始下标那排序通常都是可以接受的。三数之和、四数之和就是这样你关心的是数值组合而非位置信息。但四数相加II不一样它让你从四个数组里各挑一个数看起来好像也可以排序排序数组本身不影响结果正确性但问题是排序并不能像双指针那样帮你降低复杂度因为四个数组仍然是独立的双指针没法跨数组形成单调区间。贸然排序只会增加无谓的O(n log n)开销。所以我的判断流程大概是先问题目要返回集合本身还是集合数量再问是否涉及“同一数组内多个元素组合”如果答案是“同一数组内组合”考虑排序双指针如果答案是“多个独立数组”考虑分组哈希表。这个流程不能保证100%命中最优解但能让你在面试的紧张状态下快速找到一个方向比当场瞎试强得多。3.2 去重操作的三个常见翻车现场去重是这几道题真正的分水岭。我总结过学员最容易翻车的三个地方每次都值得拿出来说第一个翻车现场外层循环用if nums[i] nums[i 1]: continue。这会导致你跳过一些原本合法的组合。举个例子数组是[-1, -1, 2]target是0唯一合法三元组就是(-1, -1, 2)。如果i0时你去比较nums[0]和nums[1]发现都是-1就跳过了这个合法结果就永远找不到了。正确的去重是在处理完当前值后用while nums[i] nums[i - 1]来跳过后续重复的起点。第二个翻车现场内层指针去重时跳过重复后没有再多走一步。参考前面三数之和的代码在while跳过重复值后必须再执行left 1和right - 1。如果忘了left或right仍然指向已经处理过的值虽然逻辑上不影响正确性但会导致死循环或者同一个组合被重复添加。第三个翻车现场把去重放在添加到结果之前而不是之后。去重必须发生在你已经成功找到一组结果之后因为只有找到结果时你才知道当前left和right指向的值已经“用过一次”了后续再遇到相同值必须跳过。如果你一进循环就无脑去重可能会漏掉合法的组合。这个坑我当年自己也踩过后来总结出的规律是去重的位置永远紧跟在“处理完当前合法状态”之后而不是之前。这个原则对所有双指针去重都适用。3.3 花10分钟建立你自己的“哈希表题目识别清单”经过这一天我认为每个刷题的人都应该建立一套自己的识别清单。我的清单是这样写的是否存在多组数据需要配对如果是考虑分组哈希表。是否涉及统计元素出现次数且数据范围已知且固定如果是考虑数组代替字典。是否需要在单一数组内找组合且去重如果是优先考虑排序双指针。是否只关心“是否存在”而不关心“有多少”或“具体哪个”如果是可以用set。是否有键值对应关系需要快速查找如果是用字典但要注意value存什么次数、下标、组合由题目要求决定。这套清单花不了多少时间但能把你的思考路径固定下来。我见过太多人刷题靠感觉看到题就上手写代码写到一半发现解法不好再推翻重来非常浪费时间。先花三分钟想清楚方向再动手写效率能提升一大截。4. 一天训练营下来最常见的疑问与排查经验4.1 为什么我的四数相加结果总比答案少或者多这个问题绝大多数情况下出在value的存储语义上。哈希表的value存的到底是“组合出现的次数”还是“有没有出现”决定了你能不能在第二段循环中直接累加。如果用set存储两数之和那么当A、B两两组合出现多个相同和的时候set只保留一个最终结果就会比答案少。反之如果你统计次数时把相同和的不同组合都分别加一那查询的时候累加次数就是对的。有一个很容易被忽略的细节count_map[s] count_map.get(s, 0) 1这行代码看起来简单但它默认了同一个和会被多次记录。如果写成if s not in count_map: count_map[s] 1那么相同的和合并成一次查询阶段就会少统计。这个问题十个人里有三四个会犯不是不懂而是写得太快。排查方法很简单打一个日志输出每个和出现的次数是否与嵌套循环的匹配结果一致。或者直接拿小规模样例手动验证比如四个数组各两个元素总共2^416种组合手算也能核对。4.2 三数之和超时是不是我的剪枝逻辑写错了超时的原因通常不是剪枝写错而是压根没做剪枝或者去重循环写得有问题导致死循环。先看你的外层循环当nums[i] 0的时候由于数组已经排序后面的数只会更大三数之和必然大于0可以直接break。但如果target不是0这个条件就不能用。再看内层双指针如果当前三数之和大于0要让right左移小于0要让left右移。这个移动逻辑如果写反left和right就永远不会收敛循环会无限执行直到超时。这种情况调试的时候最好在循环里打印left和right当前值一看就明白。还有一种隐蔽的导致超时的情况去重循环里用了while nums[left] nums[left 1]但忘记检查left right的边界当指针碰撞时还会访问越界元素。Python虽然不会崩溃但可能读到错误值导致后续逻辑错乱。所有while去重都必须带上left right条件这是铁律。4.3 赎金信这类题用字典和用数组到底差多少说实话LeetCode的测试数据下字典和数组的耗时差距并不夸张。但在严格的面试中面试官想看的是你有没有“数据结构选择意识”。你说“字符集固定且很小所以我用数组”这句话比代码本身更能证明你的基本功。反之如果你每次碰到统计字符都用字典虽然不算错但会让人觉得你对底层数据结构理解不够细腻。我自己的判断标准是如果key是长度确定的有限枚举类型就用数组如果key是任意可哈希对象才用字典。记住这个标准你自然知道什么时候该用哪个。还有一个可以提的小技巧Python里统计字符频率如果非要用字典可以用collections.Counter它本质上就是字典的封装但代码更简洁。但训练营阶段我始终建议先用最底层的方式手写一遍这样你才能理解Counter到底帮你做了什么。4.4 四数之和里两层循环的去重分别该注意什么四数之和比三数之和多了一层循环去重容易乱。我的记忆方法是每一层循环的去重都是和“同一层上一次处理过的值”比较而不是和“下一层的起始值”比较。第一层循环i要和nums[i - 1]比因为i是第一个数的起点。第二层循环j要和nums[j - 1]比但注意这里j的起始值是i 1所以判断条件应该是j i 1的情况下才去比nums[j] nums[j - 1]。如果没有j i 1这个条件第一轮循环j等于i1时j-1等于i会和nums[i]本身比较导致第一个j被误跳过。我发现很多学员在这个地方错得非常统一就是少了j i 1的判断。只要把这个细节记住四数之和的去重问题基本解决了一大半。内层双指针的去重逻辑和三数之和完全一样不需要额外调整。整体来看四数之和其实就是三数之和的“一次封装”把三数之和的核心代码理解透四数之和是水到渠成的事。5. 任务驱动复盘Day7的实际吸收要点与扩展方向5.1 学完这一天你真正要带走的三项核心能力第一项能力是“分组降维”的思维。四数相加II表面上是哈希表题本质上是把四维问题拆成两个二维问题。这种思想在后面的很多题目里都会反复出现比如把二维矩阵的某些问题转化为一维问题把复杂条件拆成两个独立条件分别处理。学完这一天你应该能熟练地把“多数组配对”问题拆开来看。第二项能力是“排序后双指针”的操作模式。三数之和、四数之和只是这种模式的两个代表后面还有更多题目会用排序双指针去替代哈希表或暴力枚举。掌握了这个模式你在面对“组合求和”“区间统计”这类问题时就有了一个非常强力的工具箱。第三项能力是“根据数据范围选择数据结构”的判断力。赎金信告诉我们不是所有“统计字符”都要用字典。这种判断力需要反复练习才能内化但每做一道题它就会更牢固一点。5.2 后续建议把这道课的题作为模板题的延展练习我非常建议你在学完这一天后回头做几道变体题来检验掌握程度。比如把三数之和改成“最接近的三数之和”这需要你调整双指针的收敛条件把“等于target”改成“更新最小差值”。再比如把“三数之和为0”扩展到“三数之和为target”你只需要调整剪枝逻辑。这种小变化可以对冲“只会背模板”的问题帮助你真正理解每一行代码的作用。我自己带过的学员里凡是能把三数之和的代码逐行讲出为什么的后面做四数之和基本没什么障碍凡是背答案的换一个条件就乱套。刷题最忌“背过了但没理解”训练营的意义就是帮大家把“我好像会了”变成“我真的会了”。最后再分享一点个人感受哈希表Part02这一天内容确实密集难度也确实上来了但它是那种“今天痛苦明天受益”的知识点。坚持下去等你把双指针和哈希表的分工想明白了后面的很多题目会突然变得通透了。
