哈希表与双指针的取舍：四道LeetCode题彻底搞懂nSum问题

刷题计划推进到 Day7，哈希表专题进入下半程。说实话，这四道题我在不同阶段刷过不止一遍，但之前都是孤立地一道一道做，AC 完就丢到一边，过几个月再遇到又得重新想。这次跟着代码随想录的顺序重新刷，四道题放在一起，突然意识到它们根本是一道完整的思考题：什么时候该用哈希表？为什么同一个专题里，后面两道题反而要放弃哈希表改用双指针？把这个问题想明白，比 AC 掉四道题本身更有价值。

这篇文章不是单纯贴题解，重点放在四道题的横向对比和踩坑复盘上。454、383 属于哈希表的舒适区，15、18 则是哈希表从"好用"变成"鸡肋"的分水岭。我会把每道题的关键选择、去重逻辑、剪枝边界都讲透，并附上我自己写错过的例子。适合正在跟刷题计划、或者刷到三数之和四数之和卡壳的同学，读的时候建议跟着代码走一遍，比光看文字有用得多。

1. 四道题放在一起，才是哈希表完整的一课

很多人刷完这四道题的最大感受是：明明都是"几个数相加"，为什么解法差这么多？想回答这个问题，得先把哈希表的本质搞明白。

1.1 哈希表的本质：不是数据结构，而是一种"记账"思路

哈希表最核心的价值就一句话：把"查找某个元素是否存在"的时间成本从 O(n) 降到接近 O(1)，代价是额外的空间。你可以把它理解成"记账"——每看到一个元素，就把它记在一个效率极高的小本子上，之后查账就不需要翻遍整个原始账本了。

但哈希表有一个隐藏的思维定势：它擅长回答"有没有""有多少"，不擅长回答"是哪几个"。"是哪几个"这个问题一旦加上"不能重复""要去重"的约束，哈希表的优势就变成劣势了，因为哈希表天生不关心元素之间的顺序和相对位置。

这四道题的递进关系恰好印证了这一点：454 是"不同数组间配对"，383 是"存在性与计数"，这两道题里元素之间没有顺序干扰，哈希表用起来非常顺手。到了 15 和 18，要求在同一个数组内选元素，顺序和去重一下子变成核心矛盾，哈希表处理起来就会非常拧巴。

1.2 四道题的隐藏递进关系

我整理了一张表，把这四道题的差异列清楚：

从 383 到 15 是一道分水岭：一旦选择空间变成"同一个数组内部"，就必须考虑顺序和去重，解法从哈希表自然滑向双指针。这个转变很多教程没有点透，导致不少人产生"哈希表专题里为什么混进了双指针题"的困惑。

2. 454.四数相加II：把不相关的两组拆开，哈希表最舒服的用法

四数相加II 的题目是这样的：给你四个长度相同的数组，每个数组里取一个数，问有多少个四元组(i, j, k, l)使得四个数相加等于 0。

2.1 为什么这题能拆？独立性是关键

我第一次看到这道题，第一反应是四层循环，n 只要上 100 就完蛋。后来发现核心突破点在于：四个数组之间是相互独立的。从 nums1 取什么数，完全不影响 nums2 取什么数。既然相互独立，就可以把问题拆成两半：先算nums1[i] + nums2[j]的所有可能值，再把nums3[k] + nums4[l]拿来对照。

这其实就是分治思想：把四数之和拆成两个两数之和。为什么三数之和不能这么拆？因为三数之和里三个数来自同一个数组，你取第二个数时，它和第一个数之间就产生了位置关联，无法干净地拆成两个独立部分。

分组哈希的具体逻辑是：第一遍遍历 nums1 和 nums2，把每个a + b的值用哈希表记下来，value 记的是这个和出现了几次。第二遍遍历 nums3 和 nums4，计算c + d，然后去哈希表里找0 - (c + d)，找到就把对应的次数加到答案上。

这里有个细节：为什么不用 set 而是用 map？因为可能存在多个不同的(a, b)对得到同一个和，比如a+b = 1出现 3 次，那么每一个c+d = -1都能和这 3 组配对，答案要累加 3，所以必须记次数，不能只记存在性。

2.2 一趟填表，一趟查表：具体代码

class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map<int, int> umap; 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; } };

时间复杂度 O(n^2)，空间复杂度 O(n^2)。n 是单个数组的长度。

这里再补充一个选型问题：为什么用unordered_map而不是map？因为在 C++ 里，map底层是红黑树，插入和查找都是 O(log n)；unordered_map底层是哈希表，平均 O(1)。这题对有序性没有任何需求，所以哈希表完胜。如果你非要用map，在 n = 500 时可能还看不出差距，n 一旦上千，性能差距会非常明显。

2.3 这题容易暴露的常见错误

第一个坑是计数累加。我见过不少人写成if (umap.count(target)) count++，错得离谱，这等于把每个 target 只算一次，完全忽略了"同一个和出现多次"的情况。

第二个坑是从 0 开始的边界。如果四个数组长度是 0，直接返回 0，虽然代码天然支持，但面试时最好主动提一句，显得对边界敏感。

第三个是面试官常追问的变体：如果四个数都来自同一个数组怎么办？这就是 18 题四数之和的问题了——一旦变成同一个数组，就要考虑下标不能重复、结果不能重复，解法完全变了。这个问题在面试里被问到的概率不小，刷 454 的时候顺便把 18 的思想带出来，会非常加分。

3. 383.赎金信：当哈希表撞上只有26个字母的约束

赎金信其实是个很简单的题：给两个字符串 ransomNote 和 magazine，判断 ransomNote 能不能由 magazine 里面的字符构成。magazine 里的每个字符只能用一次。

3.1 为什么用数组做哈希表，比 unordered_map 快一个量级

这道题最常见的解法是用int[26]数组：因为题目明确说了只有小写字母，key 的取值范围是已知且有限的，完全可以直接用字符减去'a'映射到数组下标。这就是一个天然的完美哈希函数，没有任何冲突。

数组和unordered_map的差距在哪里？

很多人刷题时习惯性用unordered_map，根本没想过数组。但在 key 范围已知的情况下，数组是哈希表的最高效形态。顺便说一句，我在查资料时看到有文章提"哈希表开放地址法"，动态哈希表的冲突处理策略之一就是开放地址法，和这里用到的数组哈希是两码事——数组哈希压根不需要处理冲突，因为下标是唯一确定的。C++ 的unordered_map用的是链地址法而不是开放地址法，这个知识点面试偶尔会问。

3.2 先统计 magazine 还是先遍历 ransomNote？

正确顺序是：先遍历 magazine 统计每个字符出现的次数，再遍历 ransomNote，每遇到一个字符将其计数减 1，如果发现某个字符计数减成了负数，说明 magazine 里的这个字符不够用，直接返回 false。

为什么不反过来？你可以想想看：如果先遍历 ransomNote 统计需求，再去 magazine 里看够不够，逻辑上也可以，但你需要对 ransomNote 里每个字符都去 magazine 里做一次查找，而且还要注意"magazine 里同一个字符只能被用一次"这个约束，处理起来很绕。先统计 magazine 的做法，天然就把"只能用一次"变成了"计数递减"，代码简洁很多。

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; } };

3.3 一个隐藏的优化：提前剪枝

如果 ransomNote 的长度比 magazine 还长，那无论如何都不可能拼出来，直接返回 false。这行判断虽然不影响最终结果，但能省掉一次完整的统计遍历。别小看这行代码，在面试中它展示了你对问题边界的敏感度。

我在实际刷题时还犯过一个低级错误：把数组初始化为int record[26];但忘了全部置零，导致统计结果里全是随机值。刷题用的在线环境可能已经帮你处理了这个，但在本地编译器上这行= {0}必须写，这种细节平时不注意，面试现场会很尴尬。

4. 15.三数之和：为什么哈希表能做，却没人推荐？

三数之和是这四道题里最经典的一道。给一个整数数组，找出所有不重复的三元组[nums[i], nums[j], nums[k]]，满足i != j、i != k、j != k，且三数之和等于 0。

4.1 用哈希表解三数之和，去重会写到怀疑人生

理论上三数之和确实可以用哈希表解：外层固定一个数，内层用两数之和的哈希表做法找出另外两个数。但这样写会遇到两个致命问题。

第一个问题是去重。哈希表法得到的是一堆无序的三元组，[ -1, 0, 1 ]和[ 0, 1, -1 ]会被当成两个答案，你必须对每个结果排序后用 set 去重，代码瞬间变得非常冗长。

第二个问题是性能。哈希表解法的时间复杂度是 O(n^2) 不假，但常数因子比双指针大得多，因为要频繁增删哈希表元素。一旦数据量上来，哈希表方案比双指针慢不少。

所以这道题的正解是排序 + 双指针。排序的代价是 O(n log n)，但换来的是"数组有序"这个强约束，让很多问题迎刃而解。这里有一个非常重要的判断标准：只要题目要求返回的是"值"而不是"下标"，就可以排序；一旦要求返回下标，排序就会破坏位置信息，只能乖乖用哈希表。454 要求统计的是"来自四个不同数组的下标组合"吗？其实它统计的是组合个数，但四数组独立导致它可以用哈希表分组；三数之和是同一个数组内的组合，不能用哈希表分组，但返回值不要求下标，所以可以排序。这个判断标准几乎可以套用到所有类似题目上。

4.2 双指针解法：排序、固定、夹逼

核心思路：先排序，然后固定第一个数nums[i]，用左右指针left和right在 i 右侧区间内夹逼，寻找满足nums[i] + nums[left] + nums[right] == 0的组合。

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 - 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) { 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; } };

4.3 去重逻辑：最容易写错的地方

三数之和的去重是整个解题过程的灵魂，也是我见过错误率最高的地方。

先看i的去重。很多人写成if (nums[i] == nums[i + 1]) continue，这是错的。为什么？因为nums[i]和nums[i+1]相等时，nums[i+1]是left的起点，这样写会直接跳过数组中一堆相邻重复值，导致漏掉[ -1, -1, 2 ]这种合法答案。正确的是和前一个比较：if (i > 0 && nums[i] == nums[i - 1]) continue。这样处理的是"当前这个 i 对应的值已经处理过了"的情况，而不是"下一个值和我相同"的情况。

再看left和right的去重。找到一组答案后，两个指针都要移动到不相同的位置。注意这个去重发生在记录答案之后，不是在查找之前。如果先移动指针再去重，可能会漏掉指针指向重复值时仍然存在的其他答案。

最后是移动顺序。找到一组答案后，必须同时移动left和right。因为如果只动一个，新组合的和不可能是 0；如果答案的和是 0，且双指针都没越界，那只有一种解释：两个指针所指的数的和也必须是-nums[i]，只动一个就破坏了平衡。这个逻辑我当年推了半天才想明白，现在直接分享给你。

5. 18.四数之和：在三数之和面多加一层循环，剪枝的坑全变了

四数之和可以看成三数之和的升级版：给定数组和一个 target，找出所有不重复的四元组，使得四个数之和等于 target。注意这里的 target 不再是固定的 0，而是任意整数。

5.1 从三数到四数的本质变化：target 不再是 0

三数之和的剪枝可以写成if (nums[i] > 0) break，因为 target 是 0，排序后第一个数如果大于 0，后面所有数都大于 0，和必然大于 0。

但四数之和的 target 可能是负数，这时候剪枝条件就完全变了。如果还傻乎乎地写if (nums[i] > target) break，在 target 为负时会出大问题。

举个例子：nums = [-4, -1, 0, 0]，target = -5。排序后nums[0] = -4，-4 > -5如果直接用这个条件 break，就会错过[-4, -1, 0, 0]这个答案。虽然-4比 target 大，但它是负数，加上更小的负数后，总和可以变得更小，最终可能恰好等于一个负数 target。

正确的剪枝条件是：if (nums[i] > target && nums[i] >= 0) break。两个条件缺一不可——nums[i] > target保证当前值已经超过目标，nums[i] >= 0保证当前值非负，后面的数只会更大，因此后面的组合永远追不上 target。如果nums[i]是负数，它本身比 target 大并不代表后面所有的数都追不上，因为中间可能夹着更大的负数来拉低总和。

同样，内层循环对j的剪枝也要这样处理：if (nums[i] + nums[j] > target && nums[i] + nums[j] >= 0) break。这个细节是四数之和里最容易被忽视、也最容易被面试官追问的点。

5.2 去重和溢出的双重麻烦

四数之和的去重逻辑和三数之和类似，但有一个容易踩的坑：内层j的去重起点是i + 1，不是 0。所以条件是if (j > i + 1 && nums[j] == nums[j - 1]) continue。如果用j > 0判断，第二个循环会跳过i后面的第一个元素，导致漏解。

另一个麻烦是溢出。C++ 里四个 int 相加可能超过 int 范围，例如[1000000000, 1000000000, 1000000000, 1000000000]，四数之和为 4000000000，已经超过 int 的 2147483647。所以计算和时务必转成 long long，或者把 sum 声明为 long long。

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 - 3; 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 - 2; j++) { if (nums[i] + nums[j] > target && nums[i] + nums[j] >= 0) break; 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; } };

5.3 从三数到四数，最值得记住的泛化结论

我在刷完 18 之后想明白一件事：所谓 nSum 问题，本质上就是"固定前 n-2 个数，用双指针解决最后两个数"。三数之和固定 1 个数，四数之和固定 2 个数，五数之和固定 3 个数，以此类推。理论上可以递归实现，但面试中手写成 nSum 的递归代码很容易出错，而且面试官一般不会要求那么高，掌握两层循环 + 双指针的写法已经足够应对。

这是一个很实用的判断准则：当题目允许排序（即返回数组元素的值而非下标），并且要求输出所有不重复组合时，双指针是首选；当题目涉及两个独立集合之间的配对计数时，哈希表是首选。

6. 复刷这四道题后，我对哈希表题型的三点新认知

这四道题刷完，我觉得收获最大的不是背会了几种模板，而是对"什么时候不该用哈希表"有了更清楚的认识。很多新手看到"哈希表专题"就条件反射式地往哈希表上靠，结果越写越乱。

6.1 哈希表不是银弹：它把"找组合"让给了双指针

哈希表的强项是聚合计数、存在性判断、关联映射。一旦问题变成"从同一个集合中挑选多个元素组成特定值，并且要求不重复"，哈希表就会因为不擅长处理"顺序"而变得笨重。这时候排序 + 双指针反而利用了数组的有序性，把去重变成本身就能自然处理的逻辑。

我的习惯是：拿到一道题先问自己三个问题——元素来自一个集合还是多个集合？是否要求返回具体组合？有没有去重限制？如果元素来自多个独立集合，直接想哈希表分组；如果来自同一集合且要求去重，优先想双指针。

6.2 数组是哈希表的亲儿子

只要 key 的范围是已知且有限的，比如 26 个小写字母、ASCII 码范围、固定的股票代码数量，就优先用数组做哈希表。这不仅是性能上的考虑，更重要的是代码可读性和调试方便性。数组哈希本身也是"哈希表开放地址法"思想的一个极端形式——因为没有冲突，所以不需要任何冲突处理策略。C++ 中unordered_map的链地址法和它相比，在内存连续性和 cache 友好度上都是劣势。

6.3 一个比较实用的刷题顺序和复盘方法

我个人的建议是：先刷 454 和 383，感受哈希表在"计数"和"存在性"上的威力，然后刷两数之和（如果没刷过的话），再进入 15 和 18，体会为什么这两个题要切换到双指针。刷完之后，自己拿张纸画一下每道题的"数据来源"和"去重需求"，你会发现这四道题刚好覆盖了两种思路的完整光谱。

这四道题对我的最大价值，其实是逼我理解了"哈希表不是万能的"这个结论。遇到组合类去重问题，双指针往往比哈希表更优雅；遇到配对计数问题，哈希表又比双指针自然得多。能分清这两类场景，比多背十道模板题都管用。