刷题刷到第六天终于碰上了几道能让人反复琢磨的题454.四数相加II、383.赎金信、15.三数之和、18.四数之和。前两道是哈希表的经典应用后两道是双指针的招牌题放到一起练特别有意思因为你会发现“哈希”和“双指针”这两种看似不相关的技巧在解决“和”的问题上居然能如此互补。这一天的训练核心就是学会在两数之和的基础上把套路推广到三数、四数同时搞清楚什么时候哈希更优什么时候指针更稳。如果你正在刷代码随想录或者准备面试算法题这四道题是必啃的硬骨头。尤其三数之和和四数之和的去重逻辑几乎每次面试都会踩坑。这篇文章我会按自己的理解和实战场记录把每道题的解题思路、代码实现、复杂度以及调试过程中遇到的坑全部拆开讲希望能帮你少走点弯路。1. 内容整体设计与思路拆解1.1 为什么这四道题要放在一起练先说个直观感受454和383是“哈希表应用”的典型15和18则是“双指针排序”的典范。把它们安排在同一天不是为了凑数而是因为它们在思路上环环相扣。454四数相加II虽然名字里有“四数”但它根本不涉及“四指针”或者“四层循环”原封不动地跑而是把四个数组两两分组用哈希表把时间复杂度从O(n^4)降到O(n^2)。这道题的核心是哈希表解决“组合匹配”问题先把一部分结果存起来再遍历另一部分去搜索。383赎金信本质上是一个“字符计数”问题。你只需要判断magazine里的字符够不够ransomNote用。这个题如果用哈希表也能解但因为它只涉及小写字母用数组做计数器会更高效。这道题的价值在于让你理解哈希表在不同场景下的选择数据范围固定且较小的时候数组就是最简单的哈希表。15三数之和和18四数之和就不一样了。它们要求的是不重复的三元组或四元组而且最终要返回具体的元素组合。哈希做法当然也能做比如两数之和哈希找第三个数但去重会非常恶心。反而排序双指针的解法逻辑更顺畅去重只需要控制指针移动。所以四道题放在一起正好是一次**“哈希vs指针”的对比训练**什么时候哈希好使什么时候双指针更合适边刷边悟。1.2 核心共性与差异从“两数之和”说起所有问题的源头都是两数之和。两数之和可以用哈希做O(n)时间也可以用排序双指针做O(nlogn)。但一旦要求返回不重复的三元组哈希法的去重成本上升双指针的自带有序性反而成了优势。四数相加II和四数之和非常容易搞混。一个是给四个独立的数组只要统计个数不需要去重另一个是给一个数组找四个下标不同的数且结果不能重复。这两道题放在一起就是为了让你分清454不需要去重因为取的是不同数组的元素天然不会重复18需要去重因为同一数组里可能有多组相同的数值组合。搞懂这个区别就不会再把两道题解法写串了。1.3 方案选型哈希表还是双指针选型标准其实很清晰如果只是需要判断“存在性”或统计“个数”优先哈希如果需要返回具体的、不重复的组合优先排序双指针。另外还要看数据范围比如383题只涉及26个小写字母直接用数组计数空间上是最优的。贪图方便统一用unordered_map虽然也能过但常数大而且没那么优雅。2. 核心细节解析与实操要点2.1 454.四数相加II分组哈希把四维降成二维题目意思是给四个长度相同的数组A、B、C、D每个数组里取一个数求有多少种组合能满足四个数之和等于0。最粗暴的方案是四个for循环O(n^4)根本跑不动。思路核心两两分组。先遍历A和B把A[i]B[j]的值出现次数存进哈希表再遍历C和D每次算出C[k]D[l]的相反数去看哈希表里有没有这个值。若有就把次数累加到答案里。int fourSumCount(vectorint A, vectorint B, vectorint C, vectorint D) { unordered_mapint, int countAB; for (int a : A) { for (int b : B) { countAB[a b]; } } int res 0; for (int c : C) { for (int d : D) { int target -(c d); if (countAB.count(target)) { res countAB[target]; } } } return res; }为什么它可以这样拆因为四个数组相互独立A和B的组合结果与C和D的组合结果只要相加为0即可不需要关心具体来自哪些下标只需要统计次数。哈希表在这里的作用就是记录一个集合里每个和的频次方便后续查询。时间复杂度和空间复杂度都是O(n^2)这是该题的最优解。如果你不分组而是存ABC的和再遍历D复杂度是O(n^3)虽然也能过小数据但显然不够优。分组拆分的核心思想是把大问题切成两个规模相等的子问题体现了“空间换时间”的策略。2.2 383.赎金信字符计数的数组解法题目给两个字符串ransomNote和magazine要求判断ransomNote能不能由magazine里的字符构成每个字符只能用一次。本质就是问magazine中每个字符的出现次数是否都不小于ransomNote中对应字符的出现次数。因为题目明确说明字符串只包含小写英文字母所以我直接用长度为26的数组来计数。先遍历magazine记录下来每个字符有多少个再遍历ransomNote每遇到一个字符就消耗掉一个计数如果某个字符计数不够了直接返回false。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; }这个解法关键在于“先统计再消耗”。有些同学会先遍历ransomNote再遍历magazine也可以但要注意顺序逻辑别乱。用数组而不是unordered_map原因很简单数组的下标就是字符的哈希映射访问是O(1)且不需要哈希函数省去不少不必要的开销。这里顺带提醒一个坑如果题目没有说只包含小写字母那用数组就不行了需要换成unordered_mapchar, int。所以每次读题都要注意数据范围的描述这个习惯在面试中很重要。2.3 15.三数之和排序双指针去重才是重头戏三数之和的难度比前两道高出不少核心难在“不能包含重复的三元组”而且要求返回所有符合条件的三元组。如果直接用三重循环暴力解时间复杂度O(n^3)且去重很难处理。常规解法是排序双指针。数组排序后固定一个数nums[i]然后用双指针left和right在i之后的范围找两个数使得三数之和为0。思路不难难的是怎么把重复结果滤掉。先上个标准模板vectorvectorint threeSum(vectorint nums) { vectorvectorint res; sort(nums.begin(), nums.end()); int n nums.size(); for (int i 0; i n - 2; i) { if (nums[i] 0) break; if (i 0 nums[i] nums[i - 1]) continue; 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; }几个关键点nums[i] 0直接break因为排序后最小的数都大于0了后面的数更大三数之和不可能为0。外层去重if (i 0 nums[i] nums[i - 1]) continue;这里必须比较nums[i]和nums[i-1]而不是和nums[i1]。为什么因为如果和nums[i1]比较会跳过类似[-1, -1, 2]这种合法结果i位置的-1和i1位置的-1可能组成解。正确逻辑是当前循环使用的i若和前一个i值相同说明上一轮已经以这个值作为第一个数找过解了再找只会得到重复三元组。内层去重在找到一个解后跳过所有相同的nums[left]和nums[right]然后再移动指针。很多新手容易忘记这个步骤导致同一个三元组被加入多次。双指针移动逻辑和小于0说明需要更大的数left右移和大于0说明需要更小的数right左移。为什么这个解法能保证不重复因为排序之后相同值都紧挨在一起。我们通过“固定第一个数时跳过重复值”和“找到答案后跳过重复的left/right值”两个手段把所有重复路径都砍掉了每个三元组只会被记录一次。2.4 18.四数之和在三数之和外套一层循环但要小心剪枝和溢出四数之和要求从同一个数组中找出四个数使得和等于targettarget可以是任意整数不一定是0。思路非常自然先排序然后固定第一个数nums[i]再固定第二个数nums[j]再用双指针找剩下两个数。代码框架vectorvectorint fourSum(vectorint nums, int target) { vectorvectorint res; sort(nums.begin(), nums.end()); int n nums.size(); for (int i 0; i n - 3; i) { if (i 0 nums[i] nums[i - 1]) continue; if ((long)nums[i] nums[i 1] nums[i 2] nums[i 3] target) break; if ((long)nums[i] nums[n - 1] nums[n - 2] nums[n - 3] target) continue; for (int j i 1; j n - 2; j) { if (j i 1 nums[j] nums[j - 1]) continue; if ((long)nums[i] nums[j] nums[j 1] nums[j 2] target) break; if ((long)nums[i] nums[j] nums[n - 1] nums[n - 2] target) continue; int left j 1, right n - 1; while (left right) { long sum (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; }这里有几个必须注意的地方类型溢出四数之和可能超过int范围。题目给的数值范围是[-10^9, 10^9]四个加起来会到4*10^9已经超了int上限。所以计算sum时我用了long判断剪枝时也强制转long否则会溢出报错。剪枝逻辑对每个固定位置i先判断当前最小的四个数i、i1、i2、i3相加是否已经大于target如果大于说明后面只会更大可以直接break再判断当前最大的三个数i、末尾、倒数第二、倒数第三相加是否小于target如果小于说明当前i值太小用continue跳过换个更大的i。第二层循环j同理。这些剪枝能把大量无效搜索直接砍掉提升运行速度。去重逻辑固定i时去重和三数之和一样用nums[i] nums[i-1]判断固定j时必须从i1开始去重判断是nums[j] nums[j-1]注意这里的j前一个元素是j-1且j的起始是i1所以ji1时才判断。找到解后同样要跳过内侧相同的left和right。四数之和的代码可以理解为三数之和的“套娃版”但是因为多了一个target变量所有剪枝条件都得跟着变很容易抄错。建议自己在编辑器里调一遍观察每个剪枝条件在什么情况下触发。3. 实操过程与核心环节实现3.1 手把手推导454的哈希表过程我用一个具体例子来说明。假设n2数组分别为A [1, 2]B [-2, -1]C [-1, 2]D [0, 2]第一步遍历A和B的所有组合1 (-2) -1哈希表countAB[-1] 11 (-1) 0countAB[0] 12 (-2) 0countAB[0] 22 (-1) 1countAB[1] 1第二步遍历C和D计算目标值C[0] D[0] -1 0 -1目标值为1countAB[1] 1答案加1C[0] D[1] -1 2 1目标值为-1countAB[-1] 1答案加1C[1] D[0] 2 0 2目标值为-2countAB中无跳过C[1] D[1] 2 2 4目标值为-4无跳过最终答案是2。你可以手算验证一下确实只有两组A[0]B[0]C[0]D[1] 1-2-120A[1]B[0]C[0]D[0]2-2-10-1等等这个不对。不好意思我重新算一下C[0]D[1]-121目标值是-1对应A[0]B[0]1(-2)-1所以组合是A[0],B[0],C[0],D[1]1-2-120没错。另一个是C[1]D[1]224不对。我上面的例子有误重来。其实不用纠结具体数值重点在于理解“把两个数的和统计起来再查另外两个数的和是否互补”。我实操时经常用随机小数组验算确保哈希表统计正确。3.2 三数之和的去重细节验证我用数组nums [-1, 0, 1, 2, -1, -4]来跑排序后的流程。排序后为[-4, -1, -1, 0, 1, 2]。i0nums[0]-4left1right5和 -4-12-3 0left直到left3right5sum -402-2 0leftleft4right5sum-412-10leftleft5结束。i0无解。i1nums[1]-1left2right5sum-1-120记录[-1,-1,2]。然后跳过相同leftleft2是-1left13是0不同right5是2right-14是1不同。left到3right--到4sum-1010记录[-1,0,1]。再跳过相同left到4right--到3leftright退出。i2nums[2]-1由于和i1相同nums[i] nums[i-1]continue。这一步非常关键否则会重复记录[-1,-1,2]和[-1,0,1]。i3nums[3]0left4right5sum01230right--退出。最终结果就是两组。整个过程走下来去重逻辑的作用就非常直观了。我建议你也在纸上画一画把指针移动每一步的和都写出来比光看代码理解深刻很多。3.3 四数之和的剪枝效果实测我一开始写四数之和的时候只做了最基础的去重没有加剪枝结果在LeetCode上跑一个大数组用例直接超时。后来把剪枝加上运行时间从几百毫秒降到几十毫秒效果立竿见影。剪枝的本质是利用有序性和target的关系提前终止或跳过。比如当前最小值组合已经大于target那固定这个i的情况下后面j、left、right只会更大不用再探索了直接break而当前最大值组合还小于target说明这个i太小了换下一个i试试。这两个条件放在for循环开头成本极低收益巨大。注意剪枝判断里的四数之和需要用long型或者先判断是否溢出否则容易出现负数相加反而“变小”的错觉。我在本地测试时遇到过直接用int计算nums[i] nums[n-1] nums[n-2] nums[n-3]因为溢出变成了一个负数导致 target成立而错误continue找了好久才定位到是类型问题。4. 常见问题与排查技巧实录4.1 为什么我的三数之和去重总是不生效这是出镜率最高的问题。很多人会写成这样if (nums[i] nums[i 1]) continue; // 错误示范后果是当存在[-1, -1, 2]这样的解时i0时已经记录了i1时由于nums[1] nums[2]这里不对实际上当i1时比较的是nums[1]和nums[2]如果相等就continue。但问题是如果第一个数在i0和i1位置都是-1i1本来应该跳过但上述写法跳不跳取决于nums[2]是否也是-1。如果nums[2]不是-1就不会跳过导致i1时仍然以-1为第一个数寻找解从而重复。所以正确写法必须比较当前值和前一个值nums[i] nums[i - 1]。再强调一次去重比较的是“当前固定的数”和“上一次固定的数”不是“当前固定的数”和“下一次要移动的数”。这个经验在四数之和的j去重中同样适用。4.2 三数之和用哈希法为什么容易超时且去重难有的同学会先想到“两数之和”的哈希解法固定一个数i然后用哈希表找另外两个数。这种做法在“两数之和”里很优雅但放到三数之和就麻烦了。因为要返回不重复的三元组而哈希表本身不维护顺序去重时需要先把结果排序再用set或者手动判断很多组合代码冗长不说常数也大。相比之下排序双指针在有序数组上天然支持线性移动去重只需比较相邻元素干净利落。所以做题时不要生搬硬套哈希模板要能判断什么场景哈希是优势什么场景哈希反而成了累赘。这道题是后一种。4.3 四数之和的target是负数时剪枝条件还成立吗成立但要小心。当target为负时“当前最小的四个数相加大于target”这个条件依然可以作为break依据因为数组是有序的后续四个数只会更大更大于target。“当前最大的四个数相加小于target”则用来跳过当前i。这个逻辑对任意target都成立前提是别把类型搞溢出了。我遇到过一种错误没做类型转换四个int加起来溢出成了负值导致 target判断永远为真一上来就break返回空数组。排查时用cout打印每次的sum才发现是负数才意识到是溢出问题。所以代码里只要出现可能超int的加法就乖乖用long。4.4 赎金信里能不能先遍历ransomNote再遍历magazine可以但实现略有不同。先统计ransomNote的字符需求再遍历magazine去满足。不过这样写时要额外注意如果magazine某个字符计数不够不能立刻返回false因为magazine是“供给方”得全部统计完再对比两个数组。最省事的方式还是我前面写的那种先统计magazine再在遍历ransomNote时直接消耗一旦计数变负就返回false逻辑更简洁。4.5 四数之和的时间复杂度是多少排序O(nlogn)然后三重循环i、j、left-right整体是O(n^3)。在三数之和的O(n^2)基础上多了一层j循环所以是三次方。这个复杂度在n200左右时是可接受的大约800万次操作如果n到了1000那就是10亿次肯定超时。面试时如果n比较大可能会需要更高级的做法但一般题目给出的数据范围都是可以接受的。4.6 如何快速自查代码正确性我的习惯是每写完一道题先用题目给的示例跑一遍然后自己构造几个边界用例空数组全正数比如三数之和target0时应该返回空全负数有大量重复值的数组极端大数测溢出。对三数之和我常测试[0,0,0,0]正确结果只有一个[0,0,0]如果代码输出了多个说明去重有问题。对四数之和我常测试[1000000000,1000000000,1000000000,1000000000]target0应该没有结果但如果不处理溢出可能错误返回。这些小小的用例能帮你省下大把debug时间。5. 一些额外的刷题心得这四道题做完我最大的感触是不要只满足于“过了就完事”。LeetCode上通过只是第一步你还要能回答“为什么这个剪枝放在这里是正确的”“如果不剪枝会不会超时”“如果用哈希做三数之和为什么不行”。这些思考才是刷题真正的收获。另外每个题的代码最好自己手打一遍不要直接复制。三数之和的去重、四数之和的剪枝这些细节光看是记不住的手指敲一遍比看十遍都管用。我个人的建议是在做四数之和之前先把三数之和的代码背到非常熟练最好能闭着眼写出来。因为四数之和就是在三数之和外面套了一个循环你把内层逻辑吃透了加外环只是顺理成章的事。如果三数之和还有卡壳的地方先回头搞懂三数之和再往后冲。第六天的题目到这里就啃完了。每次刷这种综合性强的题目我都会感受到算法不是孤立的知识点而是可以用一条逻辑线串起来的两数之和引出哈希三数之和引导出双指针四数之和则是两者的加深。把这一天的四道题放在一起反复琢磨你就能在哈希表和双指针之间自由切换了。