刷算法题最爽的一刻就是把一个看着很唬人的题目拆成几个熟悉的小套路。今天是代码随想录算法训练营的第七天安排的四道题LeetCode454四数相加II、383赎金信、15三数之和、18四数之和恰好是哈希表和双指针两个专题的“综合检阅”。如果你正在跟着训练营打卡或者准备面试想集中突破一下这类题型这篇复盘把我的完整思考过程、代码版本和踩过的坑都整理出来了可以直接当参考。这四道题放在一天是很有讲究的454和383是哈希表的经典应用15和18则是排序双指针的重头戏。很多人在15题的三数之和去重上卡很久我也一样。这篇文章会把去重逻辑掰开揉碎讲清楚也会把四数之和里容易被忽略的剪枝和溢出问题说明白结尾再整理一份高频错误速查表希望能帮你少走点弯路。1. 训练营第七天四道题到底在练什么1.1 两两分组哈希表与双指针各占一半一天四道题看起来很密集但如果你把它们按解法分组思路马上就清楚了454四数相加II和383赎金信属于哈希表专题15三数之和和18四数之和属于排序双指针专题。题号题目核心解法时间复杂度空间复杂度454四数相加II分组 哈希表O(n^2)O(n^2)383赎金信数组模拟哈希O(n m)O(1)15三数之和排序 双指针O(n^2)O(1)不计结果集18四数之和排序 双指针 剪枝O(n^3)O(1)不计结果集注意一个很有意思的点454题名是“四数相加”18题名是“四数之和”听起来很像但解法思路完全是两个方向。454不要求去重、只要求计数可以大胆用哈希表18要求返回不重复的四元组就必须排序后配合双指针。这个差异是今天很重要的一个认知点。1.2 四道题放在一起学重点看这层递进关系从难度上观察383最简单适合热身454考察对哈希表分组的理解是哈希表用法的重中之重15的三数之和是双指针的经典题目面试出现频率极高18则是在15的基础上套了一层循环是双指针技巧的延伸应用。这四道题也暗合了代码随想录训练营前几天的学习路径先用哈希表解决“是否存在”“出现几次”这类问题再去处理“不能重复”这类需要去重的问题。训练营把这几道题放在同一天目的就是让你对比两种思路的适用场景什么时候用哈希表更高效什么时候必须排序双指针。理解了这条分界线后面遇到同类题就不容易选错方案。2. LeetCode454 四数相加II两两分组后哈希表才是主角2.1 题面拆解为什么这道题不需要去重题目给四个长度相同的整数数组 nums1、nums2、nums3、nums4要你统计有多少个四元组 (i, j, k, l) 满足nums1[i] nums2[j] nums3[k] nums4[l] 0。注意这里说的是下标组合而不是元素值组合。也就是说即使两个数组里的数字值相同只要下标不同就算不同的答案。这就解释了为什么这道题不需要去重只需要计数。还有一个隐含条件四个数组长度相同都是 n。暴力解法就是四层循环枚举所有下标组合时间复杂度 O(n^4)。如果 n 为 200200 的四次方是 16 亿直接超时。所以问题的核心就是如何避免 O(n^4)。2.2 从O(n^4)到O(n^2)分组思路是怎么来的这个思路其实很朴素把四个数分成两组。先算出 nums1 和 nums2 的所有两两之和用一个哈希表记录每个和值出现的次数再遍历 nums3 和 nums4 的所有两两之和如果哈希表里存在 0 - (c d)那就说明找到了匹配的组合把对应的次数累加到结果里。为什么这样可行因为等式可以改写为 nums1[i] nums2[j] - (nums3[k] nums4[l])。左边和右边都可以提前计算哈希表负责快速查找。我常用一个生活化类比来理解四个班要凑两队搞联谊先统计 A 班和 B 班各自在哪个时间段有空把“空闲交集”记录在表里再统计 C 班和 D 班的时间如果某个时间点在表里出现过就说明四个班这个时间都能凑上直接累加计数。这个方案的巧妙之处在于空间换时间的思路非常直接两两组合的数量是 n^2哈希表的查找平均 O(1)所以总复杂度就是 O(n^2)。对很多算法题来说把四层循环拆成两个两层循环是最朴素的降维手段。2.3 代码实现与三个容易忽略的细节class Solution { public: int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) { unordered_mapint, int umap; for (int a : nums1) { for (int b : nums2) { umap[a b]; } } int count 0; for (int c : nums3) { for (int d : nums4) { int target 0 - (c d); auto it umap.find(target); if (it ! umap.end()) { count it-second; } } } return count; } };这里有几个细节容易出问题。第一遍历 nums1 和 nums2 时umap[a b]这一句如果写成umap[a b]之后忘记累加统计频率就会错误。第二第二次循环里一定是用find去查直接用umap[target]会在 target 不存在时插入一个 0这样会污染哈希表如果第二次循环和第一次循环用的是同一个表会造成后续误判。第三count 要累加的是it-second也就是频率值而不是简单地加 1。我一开始自己写的时候最后一步写的if (umap.find(target) ! umap.end()) count;结果答案一直偏小后来才意识到同一个 target 可能对应多个 AB 的组合应该累加频率而不是加一。3. LeetCode383 赎金信用数组模拟哈希20分钟拿下3.1 题意翻译这道题和242题就差一句话赎金信的题面背景稍微有点绕but核心判断很简单给定两个字符串 ransomNote 和 magazine判断 ransomNote 能不能由 magazine 里面的字符拼出来magazine 中每个字符只能用一次。这和训练营前面做过的242有效字母异位词非常像。242那道题要求两个字符串的字符种类和数量完全一致383这道题则放宽了条件只需要 magazine 的字符能覆盖 ransomNote 即可magazine 里可以有多余的字符。所以383本质上是242的“覆盖版本”。题面还特意提醒两个字符串都只包含小写字母。这个限制条件非常关键它意味着我们不需要用 unordered_map直接用固定大小的数组就能解决问题。3.2 用数组还是unordered_map性能实测感受对于小写字母场景我用 int[26] 和 unordered_map 都实现过实际效果差别很明显。unordered_map 虽然写起来更通用但是每次插入、查找都需要计算哈希值遇到字符串较长的时候还会有扩容、内存分配的额外开销。数组模拟哈希则简单直接下标 0 到 25 对应 a 到 z值就是该字符的出现次数。26 的长度是常量空间上几乎可以忽略不计时间上就是一次数组访问效率极高。怎么选择如果在面试里遇到“只包含小写字母”这种明确限制优先用数组。如果字符集不确定或者很大再用 unordered_map。这个选择也是面试官考察代码细节的一部分能讲清楚背后的缘由会显得你对基础知识点更扎实。3.3 完整代码与复杂度说明class Solution { public: bool canConstruct(string ransomNote, string magazine) { if (magazine.size() ransomNote.size()) return false; int record[26] {0}; for (char c : magazine) { record[c - a]; } for (char c : ransomNote) { record[c - a]--; if (record[c - a] 0) return false; } return true; } };一个被很多人忽略的优化可以先判断杂志长度是否小于赎金信长度如果小于直接返回 false。这行代码虽然不影响正确性但在极端情况下能省不少时间。遍历顺序建议是先统计 magazine再遍历 ransomNote 判断够不够。如果反过来先统计 ransomNote再遍历 magazine 去扣减逻辑会绕一些也容易出现负数判定的困惑。按“库存够不够供货”的思路来写最直观。时间复杂度 O(n m)空间复杂度 O(1)。因为数组长度固定为 26不随输入规模变化。4. LeetCode15 三数之和双指针经典去重是全场重点4.1 为什么推荐排序双指针而不是哈希题目要求给定整数数组 nums返回所有和为 0 且不重复的三元组。注意“不重复”这三个字是本题的灵魂。最朴素的做法是三层循环但 O(n^3) 基本不可行。有人会想可不可以像454那样用哈希表确实可以做但你会很快发现去重非常痛苦。因为题目要求返回的是不重复的三元组也就是说顺序不同的相同三元组只能算一个。用哈希表存二元组再用 set 去重虽然也能过但代码里要处理的细节比双指针版本多得多面试时也容易被追问得漏洞百出。这就是这道题为什么推荐排序双指针方案。排序以后相同的数字会挤在一起去重变得非常自然同时通过双指针收缩区间可以一次性跳过大量无效组合。4.2 双指针移动逻辑与三处去重的正确姿势具体流程是先对数组排序然后固定第一个数 i用 left 指向 i1right 指向数组末尾计算三者之和。如果和大于0说明数值偏大right 左移如果和小于0说明数值偏小left 右移等于0 就记录答案。这里最关键的是去重而且去重有三处第一处是外层循环对 i 去重第二处是找到答案后对 left 去重第三处是对 right 去重。很多人在这里写错。先说 i 的去重。判断条件应该写成if (i 0 nums[i] nums[i-1]) continue;而不是if (nums[i] nums[i1]) continue;这两者差别非常大。我举个例子数组是 [-1, -1, 2]正确答案是 [-1, -1, 2]。如果写成nums[i] nums[i1]去重i0 时发现 nums[0] nums[1]会直接把整个组合跳过去正确答案就丢了。而写成nums[i] nums[i-1]i0 时没有前一个元素继续处理i1 时发现 nums[1] nums[0]才跳过这样保留的是每个相同数字中的最后一个位置作为固定点。简单说nums[i] nums[i-1]是确保当前固定值第一次出现时才处理nums[i] nums[i1]则是错误地跳过了需要处理的组合。再说找到答案后的 left 和 right 去重。网上代码常见的写法是while (left right nums[left] nums[left 1]) left; while (left right nums[right] nums[right - 1]) right--; left; right--;这里的顺序也很有讲究要先移动指针跳过重复值再对 left 和 right 做常规的收拢。因为找到一组答案后如果 left 右边和 right 左边有和当前值相同的元素直接跳过可以避免产生重复三元组而且不会漏掉其他组合。有人会问为什么不能在 while 循环开头就做 left 和 right 的去重因为如果还没有找到答案就贸然跳过相同值可能错过正确的组合。比如数组 [-2, 0, 0, 2, 2]固定 -2 后left 指向 0right 指向 2此时正好和为 0。但如果开头就跳过重复的 0 和 2可能直接错过这个结果。正确做法是先判断是否等于 target等于了再统一去重然后再移动。4.3 边界判断和完整实现外层循环里还有两个常规优化如果 nums[i] 0 直接 break。因为数组已经排过序第一个数大于0后面任意两个数也一定大于等于零和不可能为0了。另一个常用陷阱是 i nums.size() 但不要越界left 和 right 每次更新后要重新检查 left right。完整代码如下class Solution { public: vectorvectorint threeSum(vectorint nums) { vectorvectorint result; sort(nums.begin(), nums.end()); int n nums.size(); for (int i 0; i n; i) { if (nums[i] 0) break; if (i 0 nums[i] nums[i - 1]) continue; int left i 1; int right n - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { right--; } else if (sum 0) { left; } else { result.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--; } } } return result; } };去重是这道题真正想考察的能力如果能在面试中把三处去重为什么这么写、为什么不能那么写讲清楚这道题基本就过关了。5. LeetCode18 四数之和三数之和的套娃升级版5.1 外层套一层循环但剪枝条件完全不同四数之和的求解思路是在三数之和的基础上再套一层循环固定 i 和 j然后对剩余区间用 left 和 right 双指针。整体框架几乎一模一样唯一让人翻车的地方在剪枝。很多人在三数之和里学到了“nums[i] 0 就 break”到了四数之和想当然写成nums[i] target就 break这里有个大坑如果 target 是负数nums[i] target根本不能说明后面没有合适的组合。我举个例子nums [-4, -1, 0, 0]target -5。排序后 nums[0] -4而 -4 比 -5 大如果直接按这个条件 break就会漏掉正确答案 [-4, -1, 0, 0]。因为 target 是负数时第一个数稍微大一点后面还可以用更小的负数把总和拉回 target。代码随想录推荐的安全写法是if (nums[i] target nums[i] 0) break;也就是只有当前数字已经大于 target且当前数字本身非负时才说明后续组合不可能更小了。同理第二层循环的剪枝也写成if (nums[i] nums[j] target nums[i] nums[j] 0) break;。5.2 两个关键难点负数target与int溢出四数之和的第二个难点是溢出。nums[i] nums[j] nums[left] nums[right] 四个 int 相加在极端情况下可能超过 int 范围。比如题目给了很大的测试数据四个数都接近 2^31加起来的和直接溢出变成负数就会导致比较逻辑完全错误。解决办法很简单计算总和时用 long 类型代码里写成long sum (long)nums[i] nums[j] nums[left] nums[right];先强转一个数成 long后续相加就是 long 运算了。不能只写long sum nums[i] nums[j] nums[left] nums[right];因为等号右边是 int 先相加溢出后再把结果赋给 long已经来不及了。这是我实际踩坑时发现的一定要先把其中一个数强转。另外四数之和还多了两层去重逻辑i 的去重是if (i 0 nums[i] nums[i - 1]) continue;j 的去重是if (j i 1 nums[j] nums[j - 1]) continue;。注意 j 的起始位置比 i 大 1所以判断要去掉 j i 1 的情况否则会把第一次出现的 j 值误跳过。5.3 完整代码与剪枝优化先给出基础版本代码class Solution { public: vectorvectorint fourSum(vectorint nums, int target) { vectorvectorint result; sort(nums.begin(), nums.end()); int n nums.size(); for (int i 0; i n; i) { if (nums[i] target nums[i] 0) break; if (i 0 nums[i] nums[i - 1]) continue; for (int j i 1; j n; j) { if (nums[i] nums[j] target nums[i] nums[j] 0) break; if (j i 1 nums[j] nums[j - 1]) continue; int left j 1; int right n - 1; while (left right) { long sum (long)nums[i] nums[j] nums[left] nums[right]; if (sum target) { right--; } else if (sum target) { left; } else { result.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--; } } } } return result; } };如果想在性能上进一步优化还可以在循环开头加两组更激进的剪枝如果当前 i 与最小的三个后续数之和已经大于 target直接 break如果当前 i 与最大的三个后续数之和小于 target直接 continue。代码如下if ((long)nums[i] nums[i 1] nums[i 2] nums[i 3] target) break; if ((long)nums[i] nums[n - 3] nums[n - 2] nums[n - 1] target) continue;这两行属于锦上添花面试时提出来会显得你对极限情况考虑得更周到。不过写的时候要小心数组越界确保 i 3 和 n - 3 都在合法范围内。6. 实操心得我刷完四题的复盘与避坑记录6.1 高频错误Top5速查表这四道题刷下来我总结了一份高频错误速查表都是自己在做题或调试时真实遇到过的按出现频率从高到低排列错误类型涉及题目典型表现正确做法454结果少算454count 每次都只加1累加 it-second 频率值454误用下标访问454用 umap[target] 判断存在插入脏数据用 find 判断后累加383未判断长度383magazine 比 ransomNote 短时多跑循环先判长度直接返回 false15去重位置错误15在 while 开头对 left/right 去重错过答案在找到一组答案后再去重18溢出18四个 int 相加结果溢出判断出错计算时先强转一个数为 long18负数剪枝失误18nums[i] target 就 break漏掉正确答案改成 nums[i] target nums[i] 06.2 我平时排查这类题的调试方法如果你卡在某个用例上我的经验是别急着看题解先做三件事。第一最小化测试。把数组缩小到三四个元素手动跑一遍逻辑看是哪一步判断出了问题。比如三数之和我经常用 nums [-1, 0, 1, 0] 这种带重复值的简单用例能很快暴露去重位置写错的问题。第二打印关键指针值。在 while 循环里打印 i、left、right 和当前 sum会非常直观。尤其是三数之和这种双指针题指针移动的顺序错了通过打印一眼就能看出来。第三拿全0数组和负数target做极端测试。全0数组能检验去重逻辑比如 nums [0, 0, 0, 0] 应该只返回一个三元组 [0, 0, 0]四数之和里 target 为负数的情况也能验证剪枝是否过度。6.3 这四道题怎么刷效率最高如果按训练营的节奏走我会建议先把383这类简单题快速过掉建立信心然后集中精力啃454和15这两道代表题。454代表“哈希表分组合并”的套路15代表“排序双指针去重”的套路把这两个套路吃透18就是在15的基础上修改几行剪枝条件。四道题分配到一天里时间上大概就是383约20分钟454约30分钟15约40分钟18约40分钟剩下的时间用来复盘和整理笔记。不要追求每道题一次AC。我自己刷15题的时候去重逻辑来回改了三版才完全跑通但那之后遇到三数之和、四数之和以及后面更复杂的双指针题目都能比较快地套上模板。把错误记录下来比多刷两道新题更有价值。最后分享一个我个人的整理习惯把今天四道题的模板代码放在一个文件里用注释标注每处去重和剪枝的理由。比如15题的“nums[i] nums[i-1]”和“nums[i] nums[i1]”的区别18题的负数 target 剪枝条件454的频率累加逻辑。面试前翻一遍这个文件比重新刷十道题都管用。希望这篇复盘对你的训练营打卡也有帮助。