今天训练营进入第六天题目是454.四数相加||、383.赎金信、15.三数之和、18.四数之和。说实话前五天还在“一个数组里找东西”的阶段最多加个双指针辅助今天这四道题出来直接把哈希表和双指针两个大方向都覆盖了。我刷完第一遍的最大感受是每一道题看起来都在“找组合”但它们的约束条件不同导致解法思路完全不一样。如果你正在跟训练营或者准备系统刷 LeetCode我强烈建议你今天把这四道题放在一起去对比而不是一道一道孤立地刷。这篇文章就按我实际的刷题顺序把每一道题的思路、代码、以及我踩过的坑展开说说。1. 454.四数相加 ||与其四层循环不如两两分组1.1 题意里最关键的限定四个数组相互独立这题给你四个整数数组nums1、nums2、nums3、nums4要求统计有多少个四元组(i, j, k, l)使得四个下标对应的元素相加等于 0。注意这里不是在一个数组里找四个元素而是四个数组各取一个元素。第一次看到这题我脑子里第一个冒出来的是四层循环。四个数组长度都是 n四层循环复杂度是 O(n^4)。LeetCode 上 n 可以到几百甚至上千四层循环直接超时。那能不能减少循环层数这里有个很关键的性质四组数之间彼此独立元素的下标不会互相冲突。这意味着我们可以把前两个数组的所有两两组合先算出来再拿后两个数组的所有两两组合去匹配。这种“分组哈希”的本质是把一个大问题拆成两个中等规模的子问题。先枚举前两个数组生成一个哈希表键是两数之和值是这个和出现的次数。再枚举后两个数组每得到一个两数之和就在哈希表里找它的相反数。这样一来时间复杂度从 O(n^4) 降到了 O(n^2)空间复杂度 O(n^2)。1.2 为什么用 unordered_map 而不是排序后二分这里有人会问既然要统计“某个和出现了多少次”为什么不用 sort 二分其实也可以用排序后的数组加二分查找但有一个问题你需要统计的是一段区间里等于 target 的元素个数。如果数组里有大量重复值二分只能找到第一个和最后一个位置代码写起来并不比哈希表简单。而 unordered_map 天然支持count和find还能在 O(1) 时间内获取到 value所以这道题训练营和官方题解都倾向于哈希。class Solution { public: int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) { unordered_maplong long, int record; for (int a : nums1) { for (int b : nums2) { record[(long long)a b]; } } int count 0; for (int c : nums3) { for (int d : nums4) { long long target -( (long long)c d ); if (record.count(target)) { count record[target]; } } } return count; } };这里我特别强调long long。两个 int 相加理论上可能超出 int 能表示的范围。虽然这道题 LeetCode 的测试数据里大多数情况不会溢出但养成用long long求和的好习惯可以避免在 18 题那种四个数相加的场景里踩坑。1.3 踩坑记录map 里存的和必须是“两两和”而不是“单个值”我第一次做这题时脑子瓦特了想着先统计nums1和nums2中的每个元素出现次数再统计nums3和nums4最后用笛卡尔积的方式匹配。结果发现同样的值在不同组合里可能对应多个不同的配对方式统计起来非常麻烦而且很难去重。后来才想明白哈希表里的 key 必须是“两数之和”而不是单个元素值。你把两个元素的和作为 keyvalue 记录这个和出现了多少次后面匹配时直接乘上去就行。还有一个容易忽略的点前两个数组的和可能出现很多次相同比如nums1 [1, -1]nums2 [1, -1]那么和 0 出现了 2 次。如果后两个数组也出现某个和对应的相反数你需要把这两个次数相乘而不是简单加 1。2. 383. 赎金信简单哈希题里的边界处理2.1 题目本质是字符频次比较383 题给了你两个字符串ransomNote和magazine要求判断能不能用magazine中的字符构建出ransomNote。每个字符在magazine里只能使用一次。这题一看就是个频次统计问题统计magazine里每个字符出现的次数再查看ransomNote里每个字符需要多少次只要magazine中对应数量不小于所需数量就能构建成功。这题在训练营里被安排在第 6 天和 242 题“有效字母异位词”放在一起类比。区别在于242 要求两个字符串包含的字符种类和数量完全相同而 383 只要求magazine包含至少ransomNote所需的所有字符。2.2 用数组而不是 unordered_map 来计数题目限定了两个字符串只包含小写字母所以直接用长度为 26 的 int 数组比 unordered_map 更高效。字符c - a可以得到 0 到 25 的下标。哈希表在这个场景下不仅常数大还需要处理键值对代码也会更啰嗦。class Solution { public: bool canConstruct(string ransomNote, string magazine) { 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; } };我先遍历magazine让每个字符计数增加然后遍历ransomNote每遇到一个字符就减 1。一旦某个字符的计数小于 0说明magazine中这个字符不够用直接返回 false。如果整个循环走完都没有负数说明字符数量足够返回 true。2.3 细节空字符串和字符顺序这题另一个容易犯的错误是忽略了空字符串的情况。如果ransomNote是空串那么不管magazine是什么都应该返回 true。用上面的代码天然满足这个条件因为空串循环不会执行直接返回 true。字符顺序也需要注意。magazine里的字符顺序不影响结果因为我们是做频次统计不是判断子序列。如果你想用滑动窗口或双指针去扫描反而会把简单问题搞复杂。字符集有限时数组计数永远是这类题的最优解。3. 15. 三数之和双指针解法中最难的反而是去重3.1 为什么哈希表解法会把自己绕晕15 题要求在一个整数数组中找出所有不重复的三元组使得三数之和等于 0。很多同学包括我在刚开始刷题时第一反应是用两层循环固定前两个数再用哈希表找第三个数。逻辑上没问题但实现起来去重非常恶心。原因是数组中不可避免地存在重复值。哈希表保存的是值到下标的映射如果数组中有多个相同的值哈希表只能记录最后一次出现的下标或者需要额外维护一个计数数组。一旦出现重复值你就很难判断当前找到的三元组是不是和之前重复的。而双指针解法通过排序把相同值聚拢到一起再去重就简单多了。3.2 排序 双指针的整体框架首先对数组排序排序可以让相同的元素相邻方便去重。然后固定第一个数nums[i]用左指针指向i1右指针指向数组末尾计算三数之和。如果和大于 0说明右侧的数太大了右指针左移。如果和小于 0说明左侧的数太小了左指针右移。如果和等于 0记录三元组然后同时移动左右指针。外层从 0 遍历到n-3因为至少要留两个位置给左右指针。这里最常见的问题是去重逻辑的位置。我初始版本把去重写在了while (left right)循环最前面结果在找到合法解之前就把指针推进了漏掉了不少组合。正确做法是先判断三数之和再根据结果去重。3.3 三个位置上的去重应该如何写以nums[i]为例去重条件应该是if (i 0 nums[i] nums[i - 1]) continue;这里必须用nums[i] nums[i - 1]而不是nums[i] nums[i 1]。原因很简单nums[i]是当前作为三元组第一个元素的起点。我们要跳过的是“之前已经处理过的相同值”而不是“后面还没处理的相同值”。如果写nums[i 1]你可能把一个本来应该作为合法三元组第一个元素的位置跳过了导致漏解。找到一组合法三元组之后在移动左右指针之前也要分别跳过重复值while (left right nums[left] nums[left 1]) left; while (left right nums[right] nums[right - 1]) right--; left; right--;这两步的目的是让左指针跳过所有和当前nums[left]相同的位置让右指针跳过所有和当前nums[right]相同的位置。必须写在left和right--之前否则你在移动指针后还没跳过重复值下一轮循环就可能再次组成相同的三元组。3.4 完整代码class Solution { public: vectorvectorint threeSum(vectorint nums) { vectorvectorint result; 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) { long long sum (long long)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; } };这里有一个很经典的剪枝数组排序后如果nums[i] 0那么它右边的数都大于等于它三数之和必然大于 0直接break。这个剪枝在 target 是 0 时有效。3.5 边界条件空数组、长度小于 3、全零数组我在训练营群里见到有同学写int n nums.size();后直接for (int i 0; i n - 2; i)如果数组长度小于 3n - 2就会变成负数或 0循环可能不执行也可能因为无符号类型比较产生问题。标准写法是让循环条件足够安全或者在一开始就判断if (nums.size() 3) return {};。全零数组[0,0,0]是最容易验证去重是否写对的用例应该只返回一个三元组[0,0,0]。4. 18. 四数之和从三数到四数去重和剪枝都要重写4.1 双层循环 双指针的结构18 题和 15 题非常像只不过目标值是一个给定的target不再是固定为 0。解法也很自然地延伸先固定第一个数nums[i]再固定第二个数nums[j]然后用双指针在j1到n-1之间找剩下两个数。时间复杂度从 O(n^2) 变成了 O(n^3)。这几乎是“k 数之和”这类题的标准演化路线外层固定 k-2 个数内层双指针扫描。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 - 3; i) { if (i 0 nums[i] nums[i - 1]) continue; for (int j i 1; j n - 2; j) { if (j i 1 nums[j] nums[j - 1]) continue; int left j 1, right n - 1; while (left right) { long long sum (long 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; } };4.2 内层去重条件里的隐藏细节很多写成 15 题习惯的人会在 j 循环里写if (j 0 nums[j] nums[j - 1]) continue;但在四数之和里这是错的。因为 j 是从 i1 开始的。如果 i 位置上的值等于 i1 位置上的值内层 j 循环在第一次迭代时就会因为nums[j] nums[j - 1]而被跳过。可问题在于i和j是两个不同位置的固定数它们值相同是合法的。比如数组里有多个相同的数nums[i]取了第一个nums[j]取第二个这是完全正常的情况不应该被 continue 掉。正确写法是if (j i 1 nums[j] nums[j - 1]) continue;只有在 j 已经不是第一轮的情况下才去判断它和前一个固定数是否相同。这是四数之和和五数之和中非常容易踩的坑建议直接记下来。4.3 剪枝逻辑不能照搬三数之和三数之和里target 固定为 0所以排序后nums[i] 0可以直接 break。但四数之和的 target 是给定的可能为负数。比如 target -11数组为[-5, -4, -3, -2, 1]nums[i] -4已经大于 target但四数之和仍然是 -11能成立。所以你不能写if (nums[i] target) break这么简单的剪枝。更稳妥的剪枝方式有两种如果当前固定数加上后面最小的三个数已经大于 target可以 break。如果当前固定数加上后面最大的三个数仍然小于 target可以 continue。但实际操作中这个剪枝的代码写起来很容易出错而且对通过率提升有限。在训练营阶段我更建议先把去重和双层循环框架写对剪枝可以放到后面优化时再加。4.4 long long 在这里是必须的三数之和里三个 int 相加已经有可能溢出但概率不大。四数之和里四个 int 相加的溢出风险明显上升。LeetCode 的测试用例中数组元素范围可以达到 int 的上下界四个数相加很容易超过 int 的表示范围。我在第一次提交四数之和时直接用int sum nums[i] nums[j] nums[left] nums[right]在几个边界用例上报了 wrong answer后来查了很久才发现是溢出问题。改成long long sum后一次通过。这个坑提醒我在做求和类题目时只要涉及多个 int 相加一律先转long long不要抱侥幸心理。5. 四道题放在一起才能看出来的解题套路5.1 454 与 18 的对比独立数组 vs 同一数组把 454 和 18 放在一起看很容易产生一种“不都是四个数相加吗”的错觉。但它们的解法完全不同。454 是四个数组各取一个元素元素来源互相独立不会产生“同一个下标被重复使用”的问题。所以可以用分组哈希把四个数拆成两半用 O(n^2) 的空间换 O(n^2) 的时间。18 是在同一个数组里取四个数不仅要保证下标不重复还要保证结果不重复因此必须排序 双指针。一句话总结如果四组数来源独立优先考虑分组哈希如果在同一个数组中选数优先考虑双指针。5.2 383 与 15 的对比字符匹配 vs 数值匹配383 和 15 都是匹配问题但约束差异巨大。383 的字符集只有 26 个小写字母而且不要求输出具体的“三元组”或“下标组合”只需要判断是否能构建字符串。所以一个长度为 26 的数组就足够了。15 则要求输出所有不重复的三元组这意味着你不仅要找到解还要去重。去重问题在单纯的频次统计里很难优雅地处理所以需要排序 双指针。这也解释了为什么很多题解在讲 15 题时都要先把哈希表方案否决掉哈希表找第三个数容易但要做到“不重复”极其麻烦。去重是在三元组层面上的不是在单个数值层面上的。5.3 我今天实际刷题时的避坑清单固定数外层循环的终止条件永远是i n - k 1其中 k 是还需要选几个数。三数之和里是n - 2四数之和里是n - 3。去重判断里用nums[i] nums[i - 1]不要用nums[i] nums[i 1]。前者跳过的是已经处理过的首元素后者可能跳过合法解。双指针找到解之后左右指针的去重必须放在left和right--之前顺序不能反。四数之和的内层 j 循环去重条件是j i 1 nums[j] nums[j - 1]不要无条件写成j 0。所有关于整数求和的中间变量建议直接写long long避免无意义的溢出排查。5.4 一个可复用的通用步骤刷完这四道题后我总结了一套自己的解题顺序后面刷五数之和或者 N 数之和时也可以直接套用先明确元素来源是多个独立集合还是同一个集合。如果是独立集合优先考虑分组哈希把 k 个数拆成两组每组 k/2 个数。如果是同一个集合排序后使用多层固定 双指针。每一层固定数的去重规则都写成“和上一个固定数相同则跳过”。双指针扫到合法解后左指针右移、右指针左移前各自跳过连续重复值。这套模板不一定适用于所有变种但覆盖了今天这四道题的核心逻辑。如果你能把 15 题的双指针和去重彻底弄懂再去做 18 题基本就是机械地加一层循环唯一需要警惕的就是内层去重的起点问题。最后再说个小技巧今天做题时我自己在草稿纸上画了一个非常小的例子比如nums [-1, 0, 1, 2, -1, -4]手动推一遍双指针的每次跳转。这个方法对建立“指针移动”的感觉特别有效。不要一上来就盯着 LeetCode 的 AC 按钮先用手推一遍代码能少错很多。