1. 四数相加II454先把暴力降维再用分组聚合1.1 从四重循环到两两分组数学上的“压缩”先看题目本身四个独立数组 nums1、nums2、nums3、nums4找出所有满足 nums1[i] nums2[j] nums3[k] nums4[l] 0 的组合数量。注意这里跟后面两题不一样不要求输出具体的组合只需要计数而且每个组合里的四个元素分别来自四个数组彼此独立。这意味着一个暴力四重循环是可行的思路但 n 的上限是 200200⁴ 16 亿这个数量级在 OJ 上基本不可能通过。我第一次做这题时第一反应是“能不能把四数问题拆成两个两数问题”。为什么这样拆因为四重循环之所以慢是因为所有组合都要遍历一遍。而如果我们先把 nums1 和 nums2 的所有两两之和算出来再跟 nums3 和 nums4 的两两之和做匹配那么计算量就变成了 n² n² 2n²也就是 8 万次这跟 16 亿完全不在一个量级。这种“把多重循环拆成两个可查询的池子”的思路本质上是用空间换时间——用一个哈希表存下前两组的所有“和”及其出现次数再用后两组的和去反向查找。这里可以用一个生活化类比四个人搬砖如果随机两两配对协调工作沟通成本极高但先把前两个人所有可能的搬运方案记在账本上后两个人拿到自己的方案后直接翻账本找匹配效率一下就上来了。账本就是那个 unordered_map里面记的不只是“某和值出现了”还记“出现了几次”。1.2 哈希计数与查找的落地细节代码实现其实很短但有几个细节值得展开。class Solution { public: int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) { unordered_mapint, int umap; // 键nums1nums2的和值出现次数 for (int a : nums1) { for (int b : nums2) { umap[a b]; } } int count 0; for (int c : nums3) { for (int d : nums4) { int target -(c d); if (umap.find(target) ! umap.end()) { count umap[target]; } } } return count; } };先说为什么必须记录“出现次数”。nums1 [0, 0]nums2 [0, 0] 时a b 0 这个结果出现了 4 次。如果 map 只存 bool那么后面查找时只能加一次答案就错了。所以在第一段循环里umap[a b] 是关键不是在置 true而是累加次数。再说查找时为什么用 find 而不是直接 umap[target]。直接用方括号访问不存在的键时unordered_map 会插入一个默认值 0这会污染哈希表并且后续如果 target 恰好等于某个旧键行为没问题但对那些“不存在的键”反复查询会让表不断膨胀。更推荐先 find 再取值。这里还容易忽略的一个点外层的两个 for 循环遍历的是 nums3 和 nums4而不是 nums1 和 nums2。顺序其实可以反过来但无论哪两个数组作为第一组逻辑都一样。不过有一个小的性能感知选择哪两个数组作为“账本”理论上没有区别因为复杂度都是 O(n²) O(n²)。如果四个数组长度不一致可以让长度更小的两个数组先构建 map这样 map 的空间占用更小。1.3 我用调试踩出来的坑第一次我写的是两层循环里直接 count umap[-(c d)]忘记先判断键是否存在。结果发现如果 -(cd) 不在 map 里umap[-(cd)] 会默认插入 0count 加 0 倒是没问题但 map 里多了一堆无用键内存和查询效率都受影响。当时样例全过但跑大数据时内存用量明显偏高。后来改成 find 判断才平稳下来。另外还有个容易忽略的极端情况如果四个数组长度都是 200map 里最多会存 4 万个键这完全可接受。但如果题目要求返回具体的组合下标那这题就会变成完全不同的思路——正因为只问计数哈希分组才这么爽。2. 赎金信383字符频率统计先想清楚谁来“支付”2.1 题目背后的模型是两个字符串的频率差赎金信的题意很直接给定 ransomNote 和 magazine 两个字符串判断 ransomNote 能不能由 magazine 里的字符构成并且 magazine 中的每个字符只能使用一次。翻译成频率语言就是对于每个小写字母magazine 中该字母的出现次数必须大于等于 ransomNote 中该字母的出现次数。这不难理解但有一层隐蔽的意味这不是简单的“包含关系”而是“资源覆盖关系”。比如 magazine aabransomNote ab可以但 magazine abransomNote aab不行因为 a 不够。在做这题之前我在训练营里已经刷过几道哈希表题目。很多人一看到字符统计第一反应是用 unordered_mapchar, int这当然能过。但题目有一句容易被忽略的描述两个字符串都只包含小写字母。这意味着字母表大小是固定且极小的 26。当字典规模确定且很小时直接用数组做哈希其实比用红黑树或哈希表更合适因为数组不需要哈希函数、没有哈希碰撞、缓存命中率也高。这算是训练营里“数据范围决定数据结构”的第一次正面教材。2.2 数组哈希 vs 字典哈希不是所有哈希都要用 mapC 里的 int record[26] {0}把字符 c 映射到 record[c - a]。这个映射是天然的因为 a-z 在 ASCII 里是连续编码。为什么这个映射效率高因为一次减法就是 O(1)而 unordered_map 底层还要计算哈希值、处理可能的冲突。在 n 不大时看不出差别但当测试数据规模拉满数组方案通常比 map 方案快一倍以上。还有一点某些题解里会建议先判断 ransomNote.size() magazine.size() 就直接返回 false这是一个很小的剪枝但能让代码在极端情况下少走一轮循环。原因是构成方都不够长肯定无法覆盖目标字符串。class Solution { public: bool canConstruct(string ransomNote, string magazine) { if (ransomNote.size() magazine.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; } };2.3 消耗式检查与提前返回 false我实际写的时候最喜欢“边遍历边扣减”的处理在遍历 ransomNote 时每读到一个字符就让对应计数减一如果减完发现小于 0说明 magazine 里该字符不够用直接返回 false。这样能提前终止不需要统计完整个 ransomNote 再统一判断。这里有一个容易被新人搞混的点如果先统计 ransomNote再检查 magazine 是否覆盖就需要再遍历一遍数组看是否有负数虽然也能做但代码更啰嗦而且无法提前退出。所以这类“资源覆盖”题原则上是先处理提供方magazine再遍历需求方ransomNote。另一个易错点是把 record[c - a]-- 和判断顺序写反。比如先判断 record[c - a] 0 再减那当字符数量正好相等时也会误判为不够用。我就在编译环境里栽过一次当时觉得“先判断再扣减”是常规思路结果等于 0 时直接 false。后来改成先减后判断逻辑才对。这个小细节值得单独记一笔。3. 三数之和15哈希法在这里反而更难排序双指针才是正解3.1 为什么第一反应会想到哈希但这是条弯路做454的时候我们用哈希表把两数之和的查找优化到了 O(n²)。面对三数之和很多人的第一反应是“那我也用哈希”固定两个数然后到哈希表里找第三个数。理论上可行但这题的输出要求是三元组集合而且要求“不重复”。这个“不重复”是哈希解法最大的痛点。为什么这么说因为哈希法需要把找到的每个三元组先排序或查重才能决定要不要加入结果。而乱序数组中同一个三元组可能通过不同路径被找到多次。比如数组里有两个 -1 和两个 2固定 -1 后再找另一个 -1 和 2会重复收集到相同组合。要解决这个问题要么用 set 保存所有结果去重要么在枚举时手动跳过重复值。这两种方案都让代码变得很难写对而且一不小心就漏答案或加重复答案。另外我也试过用两层循环 set 的版本代码长度比双指针长出一截而且运行效率没有优势。这个现象背后的道理是当题目要求的具体元素组合且必须去重时哈希法的查询优势被“去重逻辑”给抵消了。所以训练营里这道题的真正解法是排序 双指针。3.2 排序解决一切去重烦恼的底层逻辑先排序的最大意义不在于让数组有序本身而在于排序后相同的元素会相邻出现。这让我们可以很容易地跳过重复元素。我们只需要规定每个位置上的数在一次遍历中只使用第一次出现的那个。比如 nums[i] 和 nums[i-1] 相等就 continue。这样从源头上避免了重复三元组的生成而不是生成后再去重。排序还有一个更深层的收益双指针的移动变得有方向性。数组升序排列后三个指针指向的值之和如果大于 0说明最右侧的值太大right--如果小于 0说明最左侧的值太小left。这种根据总和大小有方向地移动是乱序数组完全做不到的。class Solution { public: vectorvectorint threeSum(vectorint nums) { vectorvectorint result; sort(nums.begin(), nums.end()); for (int i 0; i nums.size(); i) { if (nums[i] 0) { break; } if (i 0 nums[i] nums[i - 1]) { continue; } int left i 1; int right nums.size() - 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; } };3.3 双指针的模板与两个剪枝点这段代码是后续做四数之和的基础模板我建议直接背下来但背之前一定要理解三处关键逻辑。第一处是外层剪枝nums[i] 0 时直接 break因为排序后数组是递增的nums[i] 都已经大于 0 了后面任何一个数都比它大三数之和必然大于 0继续循环没有意义。这里要区分 break 和 continue如果只是某个值导致当前循环没有答案那可能是 continue但“最小值都大于 0”意味着整个数组后半段都没希望必须 break。第二处是 i 的去重。注意条件怎么写的if (i 0 nums[i] nums[i - 1]) continue。这里对比的是 nums[i] 和 nums[i-1]不是 nums[i] 和 nums[i1]。为什么因为我们要保证“每个值第一次出现时被处理”。如果比较 i1那当遇到 nums[i] nums[i1] 时直接跳过会导致 [-1, -1, 2] 这种组合里第二个 -1 不能被使用答案就漏了。我以前一直搞混直到用一组样例手推才明白。第三处是 left 和 right 的去重位置。很多初学者会把去重写在整个 while 循环开头这是错的。比如 left 指向的值和下一个值相同如果一开始就跳过可能跳过恰好构成解的那个位置。正确答案是在找到一个合法三元组之后再收缩指针并跳过重复。因为只有收集到了一个答案才需要担心后面的重复组合在没找到答案前left 和 right 都有可能是未来合法组合的一部分不能贸然跳过。我在第一次手写这段代码时就是把 left 去重放在了循环开头结果用 [-2, 0, 0, 2, 2] 测试时直接少了一组 [-2, 0, 2]。后来按照“收集答案后再去重”的写法才完整通过。这个 bug 很典型强烈建议各位自己跑一遍这个样例感受一下。4. 四数之和18外层多套一层循环但剪枝逻辑不能照搬4.1 从三数到四数固定 i 和 j 之后又回到双指针四数之和 三数之和再套一层。核心思路是在三数之和的外面再固定一个数 i然后在剩下的区间里做三数之和其实更准确地说是固定 i 和 j 两个数把问题退化成在一个有序数组中找两数之和等于某个目标值。这里有一个非常顺滑的递进三数之和固定一个数 双指针四数之和固定两个数 双指针。每多固定一层时间复杂度就多乘一个 n。三数之和是 O(n²)四数之和是 O(n³)。n 在这里是 200 以内所以 n³ 8 百万完全在可接受范围。class Solution { public: vectorvectorint fourSum(vectorint nums, int target) { vectorvectorint result; int n nums.size(); if (n 4) { return result; } sort(nums.begin(), nums.end()); for (int i 0; i n; i) { if (nums[i] target target 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 target 0) { break; } if (j i 1 nums[j] nums[j - 1]) { continue; } int left j 1; int 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 target 为负时剪枝的隐蔽陷阱这是四数之和跟三数之和最不一样的地方。三数之和的 target 固定是 0所以 nums[i] 0 可以直接 break。四数之和的 target 是题目给定的可以是负数。如果照抄三数之和的剪枝写法if (nums[i] target) break;当 target 为负时这个剪枝是错的。举个例子nums [-4, -3, -2, -1, 0, 1]target -5。排序后 i 0 时 nums[0] -4-4 -5如果这时候 break后面所有可能的四元组都被跳过了但 [-4, -3, 0, 2]不行数组没有 2。实际上一组解是 [-4, -3, -1, 3]数组也没有 3。换一组更直接的nums [-5, -4, -3, -2, 1]target -8结果里有 [-5, -4, -1, 2]没有 -1 和 2。还是看 [-5, -4, -3, 0, 1], target -8答案包含 [-5, -4, -1, 2] 不存在但 [-5, -4, 0, 1] 和是 -8确实是一组解。此时 nums[0] -5 -8如果 break 就漏了。正解是给剪枝加上 target 0 的条件nums[i] target target 0 时才 break。为什么加这个条件因为只有当 target 非负时nums[i] 大于 target 才意味着后面所有数加起来只会更大如果 target 是负数nums[i] 可能大于 target但后面更小的数会把总和拉回 target所以不能剪。内层 j 的剪枝原理相同只是判断的是 nums[i] nums[j]。4.3 long long 与去重的额外注意点四数相加的 int 溢出是我实际运行后才注意到的坑。四个 int 相加理论上最大可以超过 21 亿比如 INT_MAX 出现在多个元素上直接加会溢出变成负数导致判断出错。所以 sum 用 long long 接收先把其中一个数转成 long long再做加法确保整个表达式按 64 位计算。去重逻辑相对顺畅沿用了三数之和的经验。但有一处细节不同j 的去重条件写的是 j i 1而不是 j 0。原因是 j 的起点就是 i 1第一次出现的 j 必须保留从第二个位置开始才考虑跳过重复值。我在刚开始写时随手写了 j 0测试样例恰好没暴露问题但换到 nums [2, 2, 2, 2, 2] 这类全重复数组时会把所有解都跳过输出空集合。这提醒我去重条件的下标边界必须根据循环的起始位置推导而不是凭习惯写。三数之和和四数之和还有一对细微区别三数之和的外层剪枝直接判断 nums[i] 0四数之和里却要先判断 target 0 再比较。我建议把这两个版本并排放在一起对照着背比单独背两个题更容易理解剪枝的本质是什么。5. 第7天的复盘哈希与双指针到底怎么选5.1 判定口诀查存在用哈希取组合用双指针四道题刷完回头看其实可以总结出一个非常实用的选择题型思路。我给自己提炼了一个判断顺序先看题目问什么。如果只要计数454说明不关心具体是哪些元素用哈希做分组聚合把查找时间复杂度压到 O(1)。如果只要判断是否可能383且字符范围固定且很小直接用数组当哈希表。如果要求返回所有具体组合且组合不能重复15、18那么优先考虑排序 双指针。原因我在三数之和部分详细论证过了具体组合 去重两件事叠加在一起哈希法的优势会被去重逻辑彻底抵消。这个判断标准还可以外推。比如后面会遇到的两数之和如果只求一个答案哈希 O(n) 就是最优。但如果要求所有不重复的二元组那排序 双指针或者排序 二分就会更合适。类似的题做多了你会发现算法选择不是看题号而是看“输出形态”。下面是四道题从数据结构和复杂度维度的快速对比我贴上来自我笔记本的表格方便各位复习时一眼扫过题号核心思路时间复杂度空间复杂度最需要注意的点454分组哈希两两聚合O(n²)O(n²)计数而非标记存在383数组模拟哈希表O(n m)O(1)先扣减再判断负数15排序 双指针O(n²)O(1) 额外空间左/右指针必须先收集答案再去重18两层固定 双指针O(n³)O(1) 额外空间剪枝必须加 target 0且 sum 用 long long5.2 复杂度心法与训练营做题顺序建议这四道题放在同一天其实是一个金字塔结构。454 是用哈希表解决两两组合的典型383 是用数组哈希解决频率统计的典型15 和 18 是双指针解决去重组合问题的典型。我建议新同学不要打乱顺序刷而是按这个顺序来先写一遍暴力解感受复杂度瓶颈再对照哈希分组解法理解空间换时间最后在 15 里集中解决去重难点18 自然就是加一层循环的机械扩展。复杂度上n 200 时 O(n³) 勉强可过如果 n 1000四数之和就得另想办法比如先做两两和的预处理再二分枚举。训练营这个阶段先不追求极致的性能优化但复杂度意识要建立起来看到 n ≤ 200可以直接估算 n³ 是 800 万次基本操作看到 n ≤ 10⁵就要下意识排除所有 O(n²) 方案。这种估算能力比记住某道题的模板重要得多它是做新题时选择算法方向的前提。5.3 一点个人心得去重逻辑永远是双指针的“案发现场”连续刷完三数之和和四数之和我去重相关的代码错误一共犯过三次第一次把 i 的去重写成和 nums[i1] 比较漏解第二次把 left 去重放在 while 入口漏解第三次把 j 的边界写成 j 0同样漏解。三次都是同一个根因没想清楚“去重应该在什么时间点、跟谁比较、从哪个下标开始”。后来我给自己定了三个检查点每次写完双指针题目都会逐一核对外层固定值的去重必须跟“前一个”比较且从索引 1 开始指针去重必须发生在“已收集一个答案”之后且必须在移动指针之前用 while 连续跳过剪枝条件里的 break必须想清楚“当前值是不是已经超出所有可能性的边界”。这三个检查点现在也分享给各位希望你们少踩我踩过的坑。第7天训练营的强度不算大但这四道题拼在一起的组合拳相当值得反复琢磨。哈希不是万能的双指针也不是银弹真正有用的是理解每种方法的适用边界。刷完这四题我从“看见哈希题就套 map”变成“先想清楚输出形态再选数据结构”这个转变本身比 AC 四道题更有价值。
工具包)
