训练营打卡第七天明显感觉到了一个分水岭——题目开始从“单点技巧”变成“组合拳”了。一天四道题454.四数相加II、383.赎金信、15.三数之和、18.四数之和看名字都带着“和”字好像都是求和题但刷完才明白这四道题其实是在训练同一个核心能力在一堆数里快速判断“某个组合是否存在/出现了几次”。差别在于有的题用哈希表舒服有的题用排序 双指针才干净。这篇文章就把我这天完整的刷题复盘写下来包括我最初想偏的地方、每道题的关键推导、以及最后整理出来的避坑清单。如果你也在跟训练营节奏刷题或者正卡在“哈希和双指针到底怎么选”这个问题上这篇应该能帮你把这四道题背后的逻辑串成一条线。1. 七天的分水岭这四道题到底在考什么1.1 为什么是“两两组合”而不是“三重循环”前六天一般还在处理数组遍历、链表翻转、哈希表基础操作第七天一下子就上四道“求和 查找”的变体题。刚看到454的时候我第一反应是四个数组各取一个数四层循环直接暴力不就行了吗好在我先顺手算了下复杂度才冷静下来——如果每个数组长度是200四层循环就是16亿次评测机不是吃素的。后来才意识到这四道题安排在同一天是有讲究的。454是“多个独立数组各取一个元素、统计组合数量”本质是把两两组合的结果存进哈希表383是“一个字符串能否从另一个字符串里凑出来”本质是字符频率的包含关系15和18则换了个方向要求在同一个数组里取不重复下标的组合并且结果集不能重复。这四道题把“查找”这个动作拆成了两种完全不同的工具哈希表回答的是“某个值出现过、出现过几次”双指针回答的是“在有序数组里哪些下标组合能凑出目标值”。真正的分水岭不是题目难度而是你开始需要判断同一类问题换一个约束条件就得换一套工具。1.2 学完这四道题你应该带走什么我的个人建议是第七天不要只求“AC四道就收工”。这四道题值得反复咀嚼的其实是下面这个判断模板题目核心场景推荐思路383字符频次是否满足要求数组哈希计数454多组数组各取一个元素统计组合数分组哈希两两合并15单数组内取不重复三元组结果去重排序 双指针18单数组内取不重复四元组结果去重排序 双层固定 双指针第一天刷的时候可能会觉得“这不都是 HashMap 能做的吗”等15题给你上一课之后你就知道HashMap 不是万能的组合去重这件事它干得很糟。后面几节我会把每道题具体怎么拆、为什么这么拆讲清楚。2. 454.四数相加II分组哈希把 O(n^4) 砍到 O(n^2)2.1 题目本质与第一直觉的错误题目给了四个长度相同的整数数组 A、B、C、D要求统计满足A[i] B[j] C[k] D[l] 0的四元组个数。注意它不要求去重不要求下标唯一之外的限制就是一个纯粹的计数题。我的第一直觉确实是四层循环。然后我看了眼题目数据范围立刻放弃了。就算每个数组长度只有200四层循环也是200^4约16亿次这在任何常规评测环境里都是不可接受的。那怎么降复杂度关键要意识到A[i] B[j] C[k] D[l] 0等价于A[i] B[j] -(C[k] D[l])。也就是说我不需要同时处理四个数我可以先把前两个数组的所有两两之和算出来存起来再处理后两个数组的所有两两之和做一次查找。这一步看着简单其实是“空间换时间”的经典操作把四元组问题降维成二元组问题。2.2 两两分组的哈希写法直接用 Python 写很快。核心是用一个defaultdict(int)记录A[i] B[j]的所有取值频率然后再遍历 C、D 的组合去查-(C[k] D[l])在不在这个频率表里from collections import defaultdict class Solution: def fourSumCount( self, nums1: list[int], nums2: list[int], nums3: list[int], nums4: list[int] ) - int: sum_map defaultdict(int) for a in nums1: for b in nums2: sum_map[a b] 1 res 0 for c in nums3: for d in nums4: target -(c d) if target in sum_map: res sum_map[target] return res写这个代码时有几个细节值得注意第一段循环建表第二段循环查表两段循环各自都是 O(n^2)所以整体是 O(n^2)。为什么用defaultdict(int)而不是普通 dict因为省掉了if a b not in sum_map: sum_map[a b] 0这种样板代码直接累加代码更干净。查询时target -(c d)注意负号别写丢了。我觉得这种负号相关的低级错误比逻辑错误更坑因为编译不报错测试一跑就错。2.3 复杂度与“为什么这里不用双指针”来个直观对比解法时间复杂度空间复杂度说明暴力四层循环O(n^4)O(1)n200 时接近16亿次运算必挂分组哈希O(n^2)O(n^2)两段 n^2 的遍历几乎是最优解有人可能会问既然15题用了双指针这题能不能也先排序再用双指针我的结论是最好别。454 的特殊性在于它统计的是四个独立数组的笛卡尔组合数量不需要去重而且“同一个值出现几次”本身就很重要。如果排序后用双指针你需要把四个数组合并成某种有序结构还要同时追踪它来自哪个数组否则下标独立性就乱了更麻烦的是双指针擅长找“唯一组合”这道题要的却是“重复计数”。让双指针去数重复组合等于把简单问题复杂化。所以这里的最优解就是哈希。这也是“多数组、各取一个、只计数”这类题目的标准套路两两分组空间换时间。3. 383.赎金信一道“温柔”的哈希计数题3.1 和异位词判断的细微区别383 的题目描述很生活化杂志magazine里的字符能不能拼出赎金信ransomNote里的内容每个字符只能用一次。本质上就是问ransomNote中每个字符的出现次数是否都不超过magazine中对应字符的出现次数。这道题如果放到训练营第九天、第十天再出现估计很多人会觉得太简单。但放在第七天其实很合适因为它是在帮你巩固一个东西哈希计数是有“方向”的。我举一个典型误区如果是“有效字母异位词”那题判断两个字符串包含的字符种类和数量是否完全一致逻辑上两边是对称的谁给谁计数都行。但383不是对称关系。magazine是“池子”ransomNote是“需求”。应该先统计池子再消耗需求如果你方向搞反了先统计ransomNote再遍历magazine去减最后还期待所有频率归零那是不对的因为magazine比ransomNote多出来的字符会留在计数器里最后你怎么检查都会误判为 false。3.2 简短实现与边界技巧先看代码class Solution: def canConstruct(self, ransomNote: str, magazine: str) - bool: if len(ransomNote) len(magazine): return False cnt [0] * 26 base ord(a) for ch in magazine: cnt[ord(ch) - base] 1 for ch in ransomNote: idx ord(ch) - base cnt[idx] - 1 if cnt[idx] 0: return False return True这里有个小技巧是提前判断长度如果ransomNote比magazine还长那无论字符分布如何肯定凑不出来直接返回 false。这不是什么高深的优化但在写代码时先做这种防御性判断能让你后面的主逻辑更干净。我实际刷题时的另一个体会是能上数组就别上 HashMap。题目明确说了字符串只包含小写字母那用长度为26的数组就是最优选择。数组本质就是一个最简单的哈希表key 是字符索引value 是频率不需要处理哈希冲突常数极小而defaultdict虽然形式优雅但每次访问都有哈希计算的额外开销。这道题规模很小HashMap 也无所谓但在面试里你如果能说清楚“字符集很小且固定所以用数组代替哈希表”会是一个很加分的细节。4. 15.三数之和双指针代替哈希去重位置决定生死4.1 为什么这道题不能照搬454的思路15题是很多人第一次感觉到“哈希表失灵”的地方。题目要求在一个整数数组nums中找出所有和为0的三元组且三元组不能重复。最常见的错误尝试是沿用454的分组哈希思路先两层循环存nums[i] nums[j]再去哈希表里找第三个数。问题出在哪一454里四个数组独立我取 A 的数不会影响取 B 的数但15题里我必须在同一个数组中取三个不同下标的数。用哈希表记录nums[i] nums[j]时找到的第三个值很有可能是当前已经用过的某个下标你得额外判断下标代码一下子就丑了。二去重非常痛苦。就算你找到了[-1, 0, 1]另一个循环里又会找到[1, -1, 0]你必须在最后对每个三元组排序然后塞进 set 去重。这等于把“查找”和“去重”硬拆开了时间和空间双重浪费。所以我最终赞同的做法是先排序再用双指针。排序这个动作看起来多花了 O(n log n)但换来了一个极其重要的性质——数组有序之后指针移动的方向是确定的。4.2 排序 双指针的完整流程双指针解法的思路可以这样想先把nums排序。固定第一个数nums[i]然后在i后面的区间里用两个指针找另外两个数。左指针left从i 1开始右指针right从数组末尾开始。计算三数之和等于0记录结果然后left右移、right左移小于0说明左指针的数太小left右移大于0说明右指针的数太大right左移。这其实就是标准的“有序数组两数之和”扩展成“三数之和”。因为数组有序当我固定nums[i]后剩余区间里找两个数的问题完全可以用双指针在线性时间内解决。一个很容易想到的优化是如果当前nums[i] 0由于数组升序后面的数都比nums[i]大三数之和不可能再等于0所以可以直接终止整个循环。核心代码如下class Solution: def threeSum(self, nums: list[int]) - list[list[int]]: 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: 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 elif total 0: left 1 else: right - 1 return res4.3 三处去重错一处就漏解我第一次写的时候第一层循环的去重写成了if nums[i] nums[i 1]: continue结果被一个经典用例打脸nums [-1, -1, 2]。仔细看排序后数组是[-1, -1, 2]。如果我用nums[i] nums[i 1]去重i 0时nums[0] nums[1]直接 continuei 1时按我的错误写法又可以进入循环然后left、right只能取2凑不出三元组。于是唯一合法的结果[-1, -1, 2]就被漏掉了。为什么因为当i 0时这个-1可以和其他元素组合而当i 1时第一个数变成了第二个-1它能选的窗口少了一个位置。一旦我在i 0时就跳过后面没人能替代它。正确的写法是if i 0 and nums[i] nums[i - 1]: continue。意思是只有当前值已经作为“第一个数”被完整处理过一遍才跳过。对比一下nums[i] nums[i 1]跳过的是“本次循环”但把下次循环需要的位置也跳掉了属于典型的错位去重。另外两处去重发生在找到解之后while left right and nums[left] nums[left 1]: left 1while left right and nums[right] nums[right - 1]: right - 1这两个 while 的作用是当nums[i]固定、且已经用当前left和right生成过一个结果后如果指针下一个位置的值和当前值相同那我再走一步生成的结果一定和刚才重复所以直接跳到最后一个相同值处。这里的去重时机也很关键。为什么一定要放在“找到结果之后”而不是一进入循环就判断因为去重的对象是“结果”不是“指针”。在匹配成功之前左侧相同值可能和右侧不同值组成不同的结果提前跳过是危险的匹配成功之后当前结果已经记录再跳过相同值只会跳过重复结果。这个“时机关联”比记死代码模板重要得多。5. 18.四数之和把“剪枝”从教科书写法改成能过的写法5.1 从三数到四数的两层固定18题是15题的直接升级给定一个数组nums和目标值target找出所有不重复的四元组使得四个数之和等于target。这里的target可以是任意整数不再固定为0。套路和15题完全一致排序固定两个数剩下用双指针。只不过15题固定一层18题要固定两层。外层i固定第一个数内层j固定第二个数然后left和right在j的右侧区间移动。时间复杂度从 O(n^2) 变成了 O(n^3)。整体代码结构和15题几乎一脉相承只要处理好两层的去重就行。但真正让我翻车的是剪枝。15题里nums[i] 0就可以 break因为target 0正数不可能和其他数加出0。18题里target不一定是0很多人包括我第一版就习惯性写成if nums[i] target: break在目标值为负数时直接漏解。5.2 负数 target 会坑掉大多数剪枝举例说明假设数组是[-5, -4, -3, 1, 2, 3]target -10。排序后nums[0] -5而-5 -10成立。如果照搬“当前数大于 target 就 break”我们立刻退出循环但实际组合-5 -4 -3 2 -10是存在的。也就是说在 target 为负时“当前数大于 target”并不能推导出“后面组合一定超过 target”因为后面还可以选更小的负数来把总和拉回去。那怎么剪枝才稳妥我后来采用的做法是不看“当前数”和 target 的粗略关系直接看“当前可用的最小四数组合”和“当前可用的最大四数组合”。对于外层i有两个安全剪枝如果nums[i] nums[i 1] nums[i 2] nums[i 3] target说明以i为起点时可选的最小四数之和都已经超过 target那后续更大的i只会让这个最小和更大直接 break。如果nums[i] nums[-1] nums[-2] nums[-3] target说明即使让i配上数组里最大的三个数都凑不够 target当前i太小换下一个i即 continue。这两个剪枝基于数组有序性而且不区分 target 的正负比nums[i] target这类条件可靠得多。内层j同理如果nums[i] nums[j] nums[j 1] nums[j 2] target在当前i下j再增大只会让最小和更大break。如果nums[i] nums[j] nums[-1] nums[-2] target当前i、j配最大的两个数都不够说明j太小continue。5.3 完整实现与溢出提醒完整代码class Solution: def fourSum(self, nums: list[int], target: int) - list[list[int]]: nums.sort() n len(nums) res [] if n 4: return res for i in range(n - 3): # 剪枝当前最小四数之和已经超过 target后面只会更大 if nums[i] nums[i 1] nums[i 2] nums[i 3] target: break # 剪枝当前 i 配上最大的三个数都不够换更大的 i if nums[i] nums[-1] nums[-2] nums[-3] target: continue # 第一层去重 if i 0 and nums[i] nums[i - 1]: continue for j in range(i 1, n - 2): # 内层剪枝 if nums[i] nums[j] nums[j 1] nums[j 2] target: break if nums[i] nums[j] nums[-1] nums[-2] target: continue # 第二层去重 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: 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 elif total target: left 1 else: right - 1 return res还有一个实际工程里很容易踩的坑整数溢出。Python 没有这个问题因为整数是任意精度的但如果你用 C 或 Java四个int相加可能超过INT_MAX导致未定义行为。C 里建议把total声明成long longJava 里建议写成long sum (long) nums[i] nums[j] nums[left] nums[right]。这类题在面试中很喜欢顺手问一句“你考虑溢出吗”所以自己写的时候养成习惯不会被问到懵。6. 第七天刷完之后的总结什么时候用哈希什么时候用双指针6.1 一条简单的判断线四道题全刷完之后我给自己整理了一条判断线后续遇到类似题基本直接套如果问题是“某个值/某种字符出现次数是否满足要求”优先考虑哈希表。字符集很小、很固定时直接上数组。如果是“多个独立集合各取一个元素统计所有组合”用分组哈希把多个集合拆成两两一组用空间换时间。如果是“同一个集合内取若干不同下标要求结果不重复”优先排序 双指针。因为只有有序环境才能用指针方向代替每一层的穷举。用这个标准回头再看第七天的四道题逻辑就非常通顺了383是纯计数454是多集合计数15和18是单集合去重组合。两条技术路线四个具体场景。更直白一点说HashMap 擅长“记数”不擅长“去重组合”。一旦题目要求“返回所有不重复的组合”哈希表的优势就变成了劣势——你不仅要处理下标冲突还要在最后做三元组排序和 set 去重复杂度反而更高。而双指针虽然在“查找某个值是否存在”的场景下不如哈希表快但它天然在有序数组上产生唯一窗口组合去重逻辑只需要几句 while 循环就能解决。6.2 四道题在考点上的迁移关系这几道题不是孤立的它们之间有很强的递进454 是“哈希分组”的典型后来的很多题目里只要遇到多数组组合计数我第一反应就是分组哈希。15 是“双指针 去重”的入门模板几乎每道“N数之和”类题目都能套这个骨架。18 则是在 15 的骨架上加了“第二层固定”和“剪枝”本质没有跳出那个套路。至于383它更像一道热身题用来提醒你哈希计数的方向问题也是面试里“字符串包含类问题”的起点。我的建议是刷完这一天后把15题的代码和18题的代码放在一起对比。你会发现从三数扩展到四数除了多了一层循环去重和剪枝的逻辑都是可以“平移”过去的。理解了这一点后面就算遇到“五数之和”“六数之和”你也知道该怎么推。7. 最后整理一份踩坑清单7.1 每道题最容易错的三件事我把这天实际踩到、或者身边同学经常踩的坑汇总成了一张表刷之前看一眼可以少走很多弯路题目常见错误正确姿势454忘记用defaultdict手动判断 key 是否存在写得很啰嗦直接用defaultdict(int)代码干净且不容易漏更新454把题目想成“去重后的组合数”偷偷加 set题目只问个数频率本身就要累加不要画蛇添足383把magazine和ransomNote的计数方向搞反先统计池子再消耗需求出现负数直接返回 false383没有先判断长度len(ransomNote) len(magazine)直接 false省掉无意义遍历15第一层去重写成nums[i] nums[i 1]写成i 0 and nums[i] nums[i - 1]否则漏解15去重时机放在“匹配成功前”放在匹配成功后跳过的是已经记录过的重复结果18照搬15题的if nums[i] 0: breaktarget 不为0必须用“最小四数和”和“最大组合”剪枝18用 C/Java 时不考虑溢出用long long/long接收四数之和这里我想单独再强调一下15题那个漏洞百出的去重位置。很多题解会直接告诉你“匹配成功之后要先 while 跳过重复值”但没有解释为什么。其实核心只有一句去重永远是针对结果的不是针对指针的。你只有先确定当前结果已经合法且已经被记录才有资格把后面相同的值安全跳过在此之前任何提前跳过都可能导致某个尚未记录的合法窗口被跳过。这个原则在18题里同样适用。7.2 给同阶段刷题人的节奏建议最后说说刷题节奏。一天四道题数量不少但第七天的四道题值得“二刷”。我自己的做法是当天 AC 之后第二天不看代码把454和15重新默写一遍。454重点看分组逻辑能不能秒反应15重点看三处去重能不能写对位置。等18题也练熟了再把15和18放在一起对比你会发现所谓“从三数到四数”其实只是多加一层固定和几个剪枝条件并没有跳出那个大的思维框架。如果你在某一道题上卡了很久别急着看题解。先把题目归个类这属于“多集合计数”还是“单集合去重组合”然后按对应的套路去套模板。第七天的这四道题本质上都是这个分类框架的练习分清楚一次后面再遇到“找两数之和、找三数之和、统计组合数”这类题你大概三秒钟就能选出该用哈希还是该用双指针了。