哈希表与双指针经典题拆解：四数相加、赎金信、三数之和、四数之和

刷题刷到哈希表这一周很多人会在同一天碰到四道很“拧巴”的题目454.四数相加II、383.赎金信、15.三数之和、18.四数之和。前两题看起来很相似后两题光看名字就劝退实际上它们放一起是有道理的哈希表的灵活用法、数组做哈希的极致选择、双指针与去重的配合、以及从三数扩展到四数的边界处理。这篇文章就把这四道题全部拆开按我自己的刷题顺序和踩坑经历重新过一遍重点说一下每一步选择的“为什么”。我默认你用 C 刷题因为训练营主推的语言版本就是它。思路本身是通用的Java、Python、Go 都能直接套。今天这份笔记适合刚刷完哈希表理论、准备开始做数组类题目的朋友也适合二刷三刷想整理去重套路的人。1. 题单整体设计与思路拆解1.1 四道题放在同一天的内在逻辑先说结论今天的前两题是“哈希表的选择题”后两题是“排序后双指针的入门题”。很多人会误以为后两题也用哈希结果越写越乱最后发现双指针才是正解。四数相加II要解决的是四个独立数组的组合问题它没有去重要求只要统计次数因此非常适合用哈希表来加速配对查找。赎金信则更简单本质上就是字符频次统计用数组就能做到极致。三数之和和四数之和同属“不重复的组合问题”一旦涉及“去重”哈希表的实现复杂度就会爆炸排序双指针反而是教科书式的解法。所以今天的题单其实是一组对照实验什么时候用 unordered_map什么时候用数组什么时候干脆排序变双指针。如果能把这道题之间的边界想清楚哈希表和双指针这两块地基就算打牢了。1.2 容器选择数组、Set、Map 到底怎么选这个点我在训练营前几天的总结里也反复提到今天再正式梳理一遍。哈希底层的容器无非三种数组、哈希集合unordered_set)、哈希映射unordered_map。数组适用于“键的取值空间很小且连续”的场景例如 26 个小写字母、ASCII 码范围内固定长度的字符。数组的查找时间是 O(1)但空间固定没有哈希函数的额外开销性能通常是最好的。哈希集合只关心“某个值是否存在”不关心出现次数。典型场景是判断一个元素是否在集合中例如两数之和的变体、链表找环。哈希映射需要统计“某个值出现了几次”或者需要根据一个键快速找到对应的值。典型场景就是四数相加II要累加满足条件的组合数量。选择错误最常见的表现值域很大还硬用数组结果造成空间浪费或者只统计次数却用集合导致组合数算不出来。今天四道题正好各占一种场景值得反复回味。2. 454.四数相加II哈希映射如何把 O(n^4) 降到 O(n^2)2.1 为什么能拆成两组题目给了四个长度相同的数组 A、B、C、D要求找元组 (i, j, k, l)使得 A[i] B[j] C[k] D[l] 0。最暴力的方案自然是四层循环复杂度 O(n^4)n 一上百就彻底完蛋。优化突破口在于如果先求 A 和 B 的所有两数之和再求 C 和 D 的所有两数之和问题就变成“两个数之和为 0”的配对问题。也就是把所有 A[i] B[j] 的值放入哈希映射并统计出现次数然后枚举 C[k] D[l] 的和去映射里找“等于 -(C[k] D[l])”的计数。这个拆法的核心思想是“分组配对”而不是“排序后双指针”。因为四个数组彼此独立没有全局有序关系也没有去重要求所以哈希映射是最直接的选择。2.2 核心代码与关键细节class Solution { public: int fourSumCount(vectorint A, vectorint B, vectorint C, vectorint D) { unordered_maplong long, int umap; for (int a : A) { for (int b : B) { umap[(long long)a b]; } } int count 0; for (int c : C) { for (int d : D) { long long target -( (long long)c d ); if (umap.count(target)) { count umap[target]; } } } return count; } };这里有几个细节值得展开。第一我刻意把键和 target 都声明成 long long原因是题目约束里的整数范围可能很大两个 int 相加理论上可能超过 int 的表示范围。虽然实际测试用例通常不会爆但刷题阶段养成用 long long 做中间运算的习惯能避免四数之和那类溢出问题在更早的题目中出现。第二umap.count(target)这步判断不能省。有人喜欢直接写count umap[target]这样当 target 不存在时 unordered_map 会自动插入一个默认值虽然结果不影响计数但会污染哈希表在重复查询中增加不必要的开销。先 count 再累加才是干净做法。2.3 复杂度与适用边界时间复杂度O(n^2)。第一个双重循环统计 AB 的所有和第二个双重循环枚举 CD 的所有和总操作量 2 * n^2。空间复杂度O(n^2)因为 AB 的组合结果最多有 n^2 种。这个题最大的启发是“四个独立数组可以拆成两组哈希”如果题目改成在同一个数组里找不重复的四元组情况就完全不同了因为它引入了“去重”和“元素不能重复使用”的限制这正是后文三数之和、四数之和要用双指针的原因。3. 383.赎金信数组做哈希的最优选3.1 题意本质与剪枝思路要求判断 ransomNote 能不能由 magazine 里的字符构成每个字符只能用一次且都只包含小写字母。翻译成计算机语言统计 magazine 中每个字符出现的次数再遍历 ransomNote每次消耗一个计数一旦出现负数说明 magazine 不够用。这里有个很容易被忽略的初始剪枝如果 ransomNote 的长度大于 magazine 的长度直接返回 false。因为即使所有字符都匹配字符总数都不够没必要继续统计。这个剪枝虽然只省掉一次哈希构建却是一个非常好的思维习惯任何“资源总量是否足够”的问题都可以先做长度判断。3.2 为什么用数组而不是 unordered_map小写字母一共 26 个键的取值空间连续且固定这是数组哈希最理想的使用场景。直接开int record[26] {0}用record[ch - a]表示对应字母出现次数省去哈希函数的计算成本和潜在的冲突处理。如果用 unordered_map虽然代码上差不多但在字符集固定的场景下属于典型杀鸡用牛刀。map 需要维护哈希表结构插入和查找都存在额外开销数组则是连续内存直接用下标访问编译优化后往往就是几条指令。我实测过很多遍数组版本跑相同数据通常比 map 版本快 20% 左右在大型字符串输入上会更明显。3.3 代码实现与额外启发class Solution { public: bool canConstruct(string ransomNote, string magazine) { if (ransomNote.size() magazine.size()) return false; int record[26] {0}; for (char ch : magazine) { record[ch - a]; } for (char ch : ransomNote) { record[ch - a]--; if (record[ch - a] 0) return false; } return true; } };有人会在第二个循环里先判断再减也可以但先减再判断更简洁。注意边界条件如果 ransomNote 为空字符串for 循环不执行直接返回 true这个行为是符合题意的。这题还顺便告诉了我们一个判断“是否构成”的通法统计一个集合的可用资源然后在另一个集合中逐个消耗一旦资源不足就提前终止。类似的题目还有判断字符串能否重排成另一个字符串、检查 t 是否是 s 的字母异位词等等。掌握了这个模式以后遇到字符限制类题目会快很多。4. 15.三数之和排序双指针去重才是灵魂4.1 先看清题目要求为什么难题目要求在数组 nums 中找到所有“不重复”且和为 0 的三元组 [nums[i], nums[j], nums[k]]i、j、k 互不相等。如果不要求去重暴力三层循环就能做但 n 的范围通常是 3000 以上O(n^3) 会超时。更麻烦的是“不重复”这三个字哪怕两个三元组只是元素顺序不同也要当成同一个结果。很多人第一反应是用哈希表去重的思路先固定一个数再在剩余部分用两数之和的哈希方法找另外两个数最后用集合去重。原理上可行但去重逻辑极其恶心因为要同时处理三个位置的大量重复情况写出来又慢又容易错。正确做法是先排序再用双指针。排序后重复元素全部相邻去重变得非常直观。这也是我看到题目后第一时间选择排序的原因。4.2 双指针的完整流程固定第一个元素 i从左往右扫。然后在 i 右侧维护左右指针 left 和 right开始时 left i 1right n - 1。计算三数之和和大于 0说明右边太大right 左移。和小于 0说明左边太小left 右移。和等于 0记录结果然后同时移动 left 和 right跳过所有重复值。因为数组已经有序右指针从最大数开始向左左指针从最小数开始向右每一步都保证不会漏掉可能的组合。这个算法的时间复杂度是 O(n^2)空间复杂度是 O(1)不考虑结果集。4.3 三个位置的去重细节这是三数之和最容易写错的地方我仔细拆开说。第一个去重位置是 i。当 i 0 且 nums[i] nums[i-1] 时直接 continue。这里必须用nums[i] nums[i-1]而不是nums[i] nums[i1]。原因在于我们是在处理“当前这个 i 作为第一个元素时是否已经处理过相同的值”。如果写成与后一个比较可能会把 i 指针直接跳到重复元素的最后一个导致漏掉一些本应记录的三元组。具体可以试一下数组[-1, -1, 0, 1, 1]按前一种写法可以正确得到[-1, 0, 1]按后一种写法很可能会重复或漏解。第二个去重位置是 left。当找到一个有效三元组后左指针可能连续遇到同样的值比如数组里有多个-1如果不跳过下一次循环又会生成相同的三元组。所以找到解后要写while (left right nums[left] nums[left1]) left;。第三个去重位置是 right思路完全对称while (left right nums[right] nums[right-1]) right--;。这里容易犯的错是在没找到解的时候也盲目去重或者在找到解后忘了最后再left; right--;。正确顺序是先记录当前解然后两个 while 跳过重复最后再移动一次指针让左右都收缩到新的位置。4.4 一个关键剪枝条件当排序后第一个元素 nums[i] 大于 0 时可以直接终止循环因为后面所有元素都大于等于 nums[i]三数之和必然大于 0。这是很自然的剪枝能节省不少时间。注意要放在 i 循环一开始判断而不是在循环外判断因为 i 不断右移排序数组后面的数越来越大。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) return result; 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) 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; } };这里我用了return result;而不是break;因为执行到nums[i] 0时后面的 i 只会更大结果集不可能再出现新解直接返回即可。5. 18.四数之和双指针的升级版5.1 从三数到四数多了一层循环四数之和要求 n 个整数中找到所有不重复的四元组 [a, b, c, d]满足 a b c d target。如果沿用三数之和的思路最外层枚举第一个数 k内层枚举第二个数 i再对剩余部分用双指针整体复杂度 O(n^3)。这看起来很自然真写起来却会遇到两个新问题二级剪枝怎么写、四个 int 加和怎么防溢出。先看代码再逐行解释。class Solution { public: vectorvectorint fourSum(vectorint nums, int target) { vectorvectorint result; sort(nums.begin(), nums.end()); int n nums.size(); for (int k 0; k n; k) { if (nums[k] target nums[k] 0) break; if (k 0 nums[k] nums[k - 1]) continue; for (int i k 1; i n; i) { if ((long long)nums[k] nums[i] target nums[i] 0) break; if (i k 1 nums[i] nums[i - 1]) continue; int left i 1, right n - 1; while (left right) { long long sum (long long)nums[k] nums[i] nums[left] nums[right]; if (sum target) right--; else if (sum target) left; else { result.push_back({nums[k], 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.2 两级剪枝的逻辑差异三数之和里的剪枝条件是排序后 num[i] 0 就可以直接返回但四数之和不能简单写nums[k] target就 break。关键在于 target 不一定是 0它可能是负数。如果 nums[k] 是负数比如 -4target 是 -10那么即使 -4 -10后面加上更大的正数也可能等于 target因此不能直接剪枝。所以最外层剪枝要写成nums[k] target nums[k] 0意思是当前数本身已经大于 target而且它是非负数那么后面所有数都不小于它四数之和必然大于 target可以 break。如果 nums[k] 是负数哪怕它大于 target后面加上正数仍有可能拉回 target不能提前结束。内层循环的剪枝同理(long long)nums[k] nums[i] target nums[i] 0。这里加了一个 long long 转换因为两个 int 相加有可能溢出虽然题目在多数测试下不会触发写出来心里踏实。5.3 去重逻辑与三数之和的差异外层去重if (k 0 nums[k] nums[k-1]) continue;。内层去重if (i k 1 nums[i] nums[i-1]) continue;。注意内层的 i 是从 k1 开始所以条件要写成i k 1不能写成i 0否则会把第一个 i 也跳过。双指针部分的去重与三数之和完全一样。这个地方如果照抄三数之和的模板整体代码写起来其实很快。所以我说四数之和是双指针的“升级版”而不是新题目难处只在于多包一层循环和多处理一个剪枝条件。5.4 溢出问题为什么必须重视四个 int 相加结果可能超过 int 能表示的最大值 2147483647。题目给的数值范围如果达到 10^9四数之和上界接近 4 * 10^9显然会溢出。我在本地写 Int 版本时遇到过某些测试用例突然算出错误结果排除了逻辑问题后才发现是溢出。所以这里有两个稳健写法一是每次计算时都显式先加 long long 转换二是直接在声明变量时就定义为 long long。我推荐前者因为声明变量为 long long 会影响后续 push_back 的隐式转换麻烦一点但不容易出错。6. 常见问题与排查技巧实录6.1 我刷这四道题时踩过的坑我把训练营群里常见的问题和我的调试记录整理成了一张速查表适合直接收藏。题目典型错误原因分析正确做法四数相加II用 unordered_set 而不是 unordered_mapset 只能判断存在无法统计次数用 map 统计 AB 和出现的次数四数相加II最后直接用 umap[target] 累加会向哈希表插入不存在的键先 count 再累加赎金信忘掉长度剪枝多跑一段无效统计先比较两个字符串长度赎金信用 map 统计 26 个字母性能和可读性都不如数组直接用 int[26]三数之和i 去重写成 nums[i] nums[i1]漏解或重复解写成 nums[i] nums[i-1]三数之和找到解后没最后移动指针产生死循环或重复解跳过重复后 left, right--四数之和外层剪枝直接写 nums[k] targettarget 为负数时会漏解必须加 nums[k] 0 条件四数之和四 int 求和溢出中间结果超过 int 范围先转 long long 再相加6.2 一套去重模板直接抄从今天后两题总结出来的双指针去重模板分享给你直接套用固定一个外层元素后让 left 当前外层下标 1right n - 1。循环里先判断当前 sum 与 target 的大小关系根据大小移动右指针或左指针。只有找到和目标相等的组合时才考虑去重先保存当前解然后两个 while 分别跳过与当前 left、right 值相等的重复元素最后统一 left 和 right--。这套模板适用于三数之和、四数之和、以及后续会遇到的“最接近的三数之和”等双指针组合类题目。记住一个口诀外层去重用跟前一个比找到解去重用跟前一个后一个比。6.3 今天题单的整体收获刷完这四道题我最明显的感受是哈希表不是万能的双指针也不是万能的。四数相加II如果硬套双指针因为数组是独立的你没办法在一个全局有序数组里移动指针三数之和如果硬套哈希去重复杂度会让人崩溃。选择算法的第一步永远是看题目条件元素是否可重复使用、是否要去重、数组之间是否有序关联。另外我在写四数之和时反复提醒自己先解决“正确性”再考虑“剪枝”。很多新手一上来就加了一堆剪枝条件结果逻辑错误一堆。其实一个不加剪枝的版本也能 AC只是慢一点。先把模板跑通再逐步添加剪枝排查起来会舒服很多。最后分享一个小技巧这几道题的代码最好独立手写三遍。第一遍照着思路写第二遍合上答案写第三遍用不同的语言或写法重新组织。等你能在三分钟内无错写出三数之和的完整代码今天的题单就算真正消化了。算法这条路没有捷径但把每道经典题磨透后面的题目会越刷越顺。