刷算法题最容易出现的情况就是：昨天还觉得自己是天才，今天一上来四道题直接被打回原形。第6天这个组合，前两题是哈希表热身，后两题直接跳进双指针去重地狱。四道题放一起练其实是有讲究的，刚好把两套核心思想串起来——哈希表管计数查重，双指针管有序数组的收敛搜索。今天这篇就把四道题从头到尾拆一遍，解法、代码、踩坑点全部摊开说。
1. 四道题放在同一天练的用意
1.1 按知识点拆解这四道题
如果只看题目名，会以为今天是哈希表专场。454和383确实是教科书级的哈希表应用，但15和18其实是排序加双指针的经典题目。这两套思路在解题体系里经常混在一起出场，尤其三数之和这道题，用哈希法做是一种路径，用双指针做是另一种路径，两者在赛场上都会遇到。
四道题的内在关系是这样：
- 454 四数相加II：哈希表的核心价值是 O(1) 查存，配合分组思想把四层循环压成两层。
- 383 赎金信：哈希计数，或者直接用数组计数，难度最低但边界细节容易踩漏。
- 15 三数之和：排序数组上的双指针收缩，难点在去重时机和指针移动逻辑。
- 18 四数之和：三数之和的升级版，多套一层循环，难点在剪枝边界和数值溢出。
这四道题练完，基本把哈希表应用和双指针收敛的两个大方向都覆盖了，而且难度是阶梯式上升的，正好一天之内从舒适区拉到崩溃边缘。
1.2 刷这四道题需要的前置基础
开始之前，至少要有这些底子：会写基本的循环遍历，理解数组下标和值的对应关系，会用手写哈希表或语言自带哈希结构，能理解排序的基本作用。如果还没接触过排序算法也没关系，直接用库函数排序就行，这四道题核心不在排序本身，而在于排序之后双指针才能发挥威力。
另外，C++ 选手需要熟悉 unordered_map 的用法，包括插入、查找、计数累加这三个操作。Java 选手对应 HashMap，Python 选手准备字典就行。底层原理不需要深度学习，但要知道哈希表查询是平均 O(1)。
2. 454.四数相加II：分组哈希把 O(n^4) 降到 O(n^2)
2.1 暴力思路为何走不通
四个数组 A、B、C、D，每个取一个数，求和为零。最直观的思路就是四层循环嵌套，枚举所有组合再统计和为零的数量。假设每个数组长度是 n，四层循环就是 O(n^4)。n 如果是 200，那计算量就是 16 亿次组合。在多数在线评测系统中，这个量级的运算已经不保险了，尤其在循环内部还要做条件判断，实际跑起来很容易超时。
就算不超时，这个思路也没有任何练习价值，因为完全没用到任何数据结构技巧，纯粹靠硬算。
2.2 两两分组的核心思路
把四个数组拆成两组：先算出 A 和 B 中所有元素两两相加的结果，用哈希表记录每种和出现的次数。再遍历 C 和 D 中所有两两相加的结果，如果结果在哈希表中能找到对应值，就知道有多少种组合能让四数之和为零。
举个例子，如果 A[i] + B[j] = 3，那么在哈希表里 3 对应的计数加一。然后遍历 C 和 D，如果 C[k] + D[l] = -3，那就说明当前这一步能找到 counter[-3] 种组合，把计数累加进答案。因为只要 A+B=3 和 C+D=-3，无论具体是哪个下标组合，四个数的和一定是零。
这个过程把四层循环拆成两个两层循环，时间复杂度降为 O(n^2)，空间复杂度也是 O(n^2)，因为哈希表最多存 n 的平方种组合。
2.3 代码实现与关键细节
class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map<int, int> hash; for (int a : nums1) { for (int b : nums2) { hash[a + b]++; } } int count = 0; for (int c : nums3) { for (int d : nums4) { int target = -(c + d); if (hash.find(target) != hash.end()) { count += hash[target]; } } } return count; } };这段代码里有几个值得注意的地方。第一，哈希表统计的是两个数的和出现的次数，不是只记录某个和是否存在，因为这个题要求统计组合数量，所以计数信息比存在性更重要。第二，遍历 C+D 时没有修改哈希表，只是在查表，所以不用担心遍历过程中哈希表变化影响结果。第三，负号要加在 c+d 的整体上，写成 -(c+d)，而不是 -c + d，一个经典的初学者错误是符号处理错误导致统计结果偏差。
注意：hash.find(target) 和 hash.count(target) 都可以判断键是否存在，但如果需要读取对应的计数，用 find 更顺手。直接用 hash[target] 去读会有副作用——如果键不存在，它会被自动插入并初始化为 0，虽然结果可能碰巧正确，但会污染哈希表内容，而且改变哈希表结构本身就不是好做法。
2.4 为什么不是分成 1+3 而不是 2+2
有人会想，既然可以两两分组，那也可以拿 A 和 B 和 C 先凑出所有三元组合，哈希表记录三元组合的和，然后遍历 D 去找负数。这个思路理论可行，但复杂度是 O(n^3)，空间复杂度也是 O(n^3)。当 n=200 时，哈希表需要存 800 万个键值对，内存直接吃紧，时间也比 O(n^2) 慢一个量级。
两两分组是时间复杂度和空间复杂度的最优平衡点。这条经验可以作为通用策略记下来：凡是涉及四组数据的组合问题，先尝试 2+2 分组，而不是 1+3 或 3+1，除非有其他限制条件，否则两两分组的性价比几乎总是最高的。
2.5 这道题的变体思路与误区
有个常见误区是把四数相加II和三数之和混为一谈，觉得都用双指针。实际上这道题返回的是组合数量，而不是三元组列表，正因为只统计数量，哈希表记录计数才足够。如果题目改成返回所有下标组合，哈希表的方案就不可行了，因为要去重会非常麻烦。这种题型变化带来的思路切换，在面试中很常见，值得提前想清楚。
3. 383.赎金信：一道被低估的哈希计数题
3.1 题意澄清：字符不能重复使用
赎金信题目的意思是用杂志上的字符拼出赎金信，杂志的每个字符只能使用一次。判断方式是：ransomNote 中每个字符出现的次数，必须小于等于 magazine 中对应字符出现的次数。这本质上是一个多重集合的包含关系判断。
一个容易忽略的条件是，题目默认输入都是小写英文字母。这直接决定了用固定大小数组就能解决问题。如果输入扩展到任意 Unicode 字符，数组方式就不适用了，需要用真正的哈希表。先看清题目约束再选数据结构，是这道题想传达的核心思维方式。
3.2 为什么用数组而不是 unordered_map
由于字符集固定为 26 个小写字母，创建一个长度为 26 的数组就能完成所有计数工作。数组的下标对应字符，数组的值对应该字符出现的次数。用 unordered_map 当然也能做，但在这种字符集极小且已知的场景，数组有几个明显优势：
- 数组是连续内存，访问速度比哈希表快得多，不存在哈希碰撞带来的性能损耗。
- 数组天然支持下标索引，逻辑更直观，debug 更容易。
- 空间占用固定，不会因为哈希表扩容抖动。
这个选择原则可以推而广之：当数据范围很小且是连续整数或可映射为连续整数时，用数组代替哈希表。在网络编程里，统计请求头里的状态码、统计端口号等场景，这个技巧同样适用。
3.3 完整实现与边界条件
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 消耗字符数量，当某个字符被消耗成负数时，说明杂志上的字符不够用，直接返回 false。
有一个小巧思：先检查 ransomNote 的长度是否大于 magazine 的长度，如果大于，直接返回 false，根本不需要进入计数循环。这个剪枝看起来简单，但在实际刷题中能帮助你建立边界条件的敏感度。因为如果一个字符串比另一个更长，它一定不可能完全由另一个字符串的字符构成，因为字符不能重复使用。
注意：初始化为 {0} 的操作在 C++ 里会把数组全部元素置零，漏掉这个初始化会导致未定义行为，因为栈上数组的初始值可能是随机数。这是初学者最长踩的坑。
4. 15.三数之和：排序加双指针，坑全在去重
4.1 为什么哈希法做三数之和很难受
三数之和的正规解法有三个主流思路：哈希辅助的两重循环、排序后双指针、暴力剪枝。哈希法看起来能解决查找问题，实际处理起来很别扭。当找到两个数，去哈希表里找第三个数时，确实能找出来，但去重非常麻烦。因为你可能得到重复的三元组，比如 [-1, 0, 1] 和 [0, -1, 1] 是同一组，哈希法返回的集合中这种重复非常多，需要额外引入 set 去重，而 set 去重又会增加时间和空间开销。
另一个问题是题目要求返回三元组列表，而且不能包含重复三元组。哈希法天然不擅长处理这种“结果集合去重”的需求，因为哈希表擅长的是快速判断存在性和计数，而不是维护有序的唯一集合。
所以这道题最推荐的解法是：排序加双指针。排序让数组有序，顺序信息帮助去重，双指针帮助在有序数组上快速收敛左右边界。
4.2 双指针解法的主流程
算法框架分三步：排序、固定一个数、双指针找剩下的两个数。
先把数组升序排序。然后外层循环固定第一个数 nums[i]，用左指针 left 指向 i+1，右指针 right 指向数组末尾。此时问题转化为在有序数组的 [left, right] 区间内找两个数，使其和等于 -nums[i]。双指针在这个有序区间上不断收缩：
- 如果 nums[i] + nums[left] + nums[right] == 0，记录结果，同时移动左右指针。
- 如果和大于 0，说明 nums[right] 太大了，右指针左移。
- 如果和小于 0，说明 nums[left] 太小了，左指针右移。
这个流程有点像在一个排序的价格区间里，不断调整两端的偏移来匹配目标值。因为数组有序，移动指针的方向是确定的，不会来回震荡，所以每个元素至多被左右指针各访问一次，额外时间复杂度是 O(n)。外层固定一个元素要遍历 O(n) 次，所以总体时间复杂度 O(n^2)。
4.3 去重的完整逻辑
这道题最核心也是最容易写错的地方是去重。去重主要涉及三个位置：外层循环的 nums[i] 去重、找到一组解后的 nums[left] 去重、nums[right] 去重。
外层去重写法：
if (i > 0 && nums[i] == nums[i - 1]) { continue; }为什么是和前一个比较而不是和后一个比较？因为 nums[i-1] 是已经处理过的数，如果当前值等于前一个值，说明当前元素能产生的所有组合，前一个元素已经全部覆盖了，直接跳过，避免重复组合。写成和 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[left+1] 相同，用新的 left 继续找还会得到同一个三元组。先跳过重复，再移动指针，顺序不能反。如果顺序反了，写成：
left++; while (left < right && nums[left] == nums[left - 1]) ...效果其实一样，但前者语义更清晰，推荐前者。
4.4 完整参考代码
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> 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) { 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--; } else if (sum < 0) { left++; } else { right--; } } } return result; } };这里有一个小优化：排序之后如果 nums[i] 已经大于 0，可以直接 break 退出循环，因为后面的数都比 nums[i] 大，三数之和永远大于 0。
4.5 这道题的真实面试情况
三数之和在真实面试中出现的频率相当高。它不考你知不知道某个高级算法，而是考你在数组处理中如何处理边界和去重。很多候选人能快速写出主体逻辑，但会在去重细节上失分。尤其两个细节经常被追问：一是为什么外层去重比较 nums[i] 和 nums[i-1] 而不是和 nums[i+1]，二是找到一组解之后为什么还要二次去重。这两个问题回答清楚了，基本就能说明你真的理解了这个算法的本质。
5. 18.四数之和：三数之和套一层壳，剪枝别踩负数坑
5.1 从三数扩展到四数
四数之和的解法就是在三数之和外面再套一层循环。外层固定第一个数 nums[i]，内层再固定第二个数 nums[j]，然后双指针找剩下两个数。整个框架完全复用三数之和的思路，只是多了一层枚举。
外层循环的规模是 O(n^3)，比三数之和的 O(n^2) 多一个量级。这是题意本身决定的，因为要找四个数的组合，至少要枚举三个自由度。
5.2 剪枝逻辑与 target 为负数的坑
四数之和的题目中 target 不是固定的 0，可能是正数、负数或零。这里有个容易踩的坑：不能直接照搬三数之和的 nums[i] > target 就 break 的剪枝。
比如 target 是 -5，nums[i] 是 -1，此时 nums[i] > target，但后面如果有 -2 和 -2，四个数之和可能是负数且等于 -5，所以直接 break 会丢掉合法组合。只有当 nums[i] 是非负数时，nums[i] > target 才能安全退出，因为非负数组递增，后续加和会越来越大。
正确的剪枝写法：
if (nums[i] > target && nums[i] >= 0) { break; }内层循环也一样：
if (nums[j] > target - nums[i] && nums[j] >= 0) { break; }这里要注意，内层剪枝的条件是 nums[j] 大于 target 减去 nums[i]，因为外层已经固定了一个数，剩余需要三个数的和达到 target - nums[i]。
5.3 双层去重与数值溢出
四数之和的去重逻辑比三数之和多一层，但原理完全相同。外层 i 去重比较 nums[i] 和 nums[i-1]，内层 j 去重比较 nums[j] 和 nums[j-1]，双指针部分复用三数之和的去重逻辑。
另一个坑是数值溢出。C++ 中 int 类型最大约 21 亿，四个 int 相加可能会溢出。在三数之和中，int 的溢出问题不明显，因为三个 int 最大值约 63 亿，已经可能溢出，但题目中的测试数据通常不会触发四位数直接超出 int 范围。到了四数之和，四个 int 相加，溢出风险显著增大，所以计算和时用 long long 类型：
long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];这个类型转换必须在相加之前发生，不能先加 int 再加 long long，因为溢出的那一刻结果已经错了。
5.4 完整参考代码
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> 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[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 long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right]; if (sum == target) { 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--; } else if (sum < target) { left++; } else { right--; } } } } return result; } };注意内层循环 j 的起始值是 i+1，去重判断是 j > i+1 而不是 j > 0，因为第一个 j 对应的前一个元素是 nums[i]，它属于外层循环固定值，不能把 nums[j] 和 nums[i] 判重。
5.5 复杂测试案例中的剪枝效果
有次我拿一个包含大量负数且 target 也为负数的案例跑这段代码，剪枝的效果非常明显。比如数组里有 -100 到 100 的所有整数，target 是 -10，如果不用负数剪枝，外层循环会一路从 -100 跑到正数区域才 break，浪费很多计算。加上了非负数判断，遇到正的 nums[i] 且比其他三个数能达到的最小值还大时，就直接跳出循环，速度提升接近一个量级。
6. 实战中的常见问题与排查记录
6.1 为什么我的哈希版本三数之和超时了
这个我在群里看到有同学问过。用哈希表辅助，两层循环枚举两个数，在哈希表里找第三个数，思路没问题，但去重依赖 set。set 的插入和查找虽然是 O(log n)，但高频调用下开销很大，而且结果太多时内存膨胀严重。更关键的是，哈希法枚举了两层循环的所有组合，即使是去重后，仍会生成大量重复组合再丢弃，这种浪费在数据规模大时非常致命。双指针版本在有序数组上天然避免重复枚举，效率明显更高。
6.2 去重写在 while 之前还是之后的讲究
还是说三数之和，找到一组解后，有两个位置可以写去重：一个是在判断 sum==0 的 if 分支里，一个是在 if 分支外统一处理。实际测试下来，写在找到解的分支里是必要的。因为只有找到合法解之后，才需要跳过重复指针，避免重复记录。如果写在 while 循环外，逻辑上也可以，但会搞得一团乱，有时候甚至错误跳过一些本应合法的新组合。
我建议的做法是：找到解后立即移动指针，在移动之前跳过重复值，而且跳过的条件要带 left < right 保护，不然可能越界访问。
6.3 数组哈希 vs unordered_map 怎么选
这个选择问题反复出现。记住一条原则：数据范围小且连续，用数组；数据范围大或稀疏，用 unordered_map。383题用数组，454题用 unordered_map，因为两个数的和可能范围非常大，数组不知道开多大。有些题目两种都能过，但数组更快，内存更小。刷题时可以都写一遍对比一下，能更直观理解差距。
6.4 关于 debug 的建议
四数之和这种去重复杂的题，用几组特殊用例验证边界是必要的。我常用的几组测试数据：
- 全零数组：[0, 0, 0, 0]
- 完全重复元素数组：[1, 1, 1, 1, 1]
- 包含负数和正数且 target 为负：[ -3, -2, -1, 0, 1, 2 ]，target = -5
- 最小长度场景：数组长度正好等于要求的元素个数
每组数据跑一遍，如果结果都能去重成功，基本说明逻辑没问题。
调试手段上，建议在去重逻辑处加临时打印，观察 left 和 right 的移动情况。因为指针移动是整个算法最容易出错的位置，直接看输出最直观。定位到问题后删除打印语句即可。
我个人在实际练习中的体会是：从第454题到第18题，核心变化不是数据结构从哈希表换成了双指针，而是从“无序集合中快速查存”切换到了“有序序列上收缩搜索”。这两套思路在工程中同样常见，比如数据库索引的原生结构就是有序树，而缓存机制大量依赖哈希表。如果把四道题当做一个整体来复盘，收获会远大于单独刷完四道题加起来的价值。每次遇到“找若干数之和满足条件”的题目时，可以先问自己三个问题：集合是否无序，结果是否需要去重，数据范围是否可排序。答案会直接指向最优解法。这套判断流程熟练之后，比记住任何一道题的标准答案都有用。
