刷题计划推进到 Day7哈希表专题进入下半程。说实话这四道题我在不同阶段刷过不止一遍但之前都是孤立地一道一道做AC 完就丢到一边过几个月再遇到又得重新想。这次跟着代码随想录的顺序重新刷四道题放在一起突然意识到它们根本是一道完整的思考题什么时候该用哈希表为什么同一个专题里后面两道题反而要放弃哈希表改用双指针把这个问题想明白比 AC 掉四道题本身更有价值。这篇文章不是单纯贴题解重点放在四道题的横向对比和踩坑复盘上。454、383 属于哈希表的舒适区15、18 则是哈希表从好用变成鸡肋的分水岭。我会把每道题的关键选择、去重逻辑、剪枝边界都讲透并附上我自己写错过的例子。适合正在跟刷题计划、或者刷到三数之和四数之和卡壳的同学读的时候建议跟着代码走一遍比光看文字有用得多。1. 四道题放在一起才是哈希表完整的一课很多人刷完这四道题的最大感受是明明都是几个数相加为什么解法差这么多想回答这个问题得先把哈希表的本质搞明白。1.1 哈希表的本质不是数据结构而是一种记账思路哈希表最核心的价值就一句话把查找某个元素是否存在的时间成本从 O(n) 降到接近 O(1)代价是额外的空间。你可以把它理解成记账——每看到一个元素就把它记在一个效率极高的小本子上之后查账就不需要翻遍整个原始账本了。但哈希表有一个隐藏的思维定势它擅长回答有没有有多少不擅长回答是哪几个。是哪几个这个问题一旦加上不能重复要去重的约束哈希表的优势就变成劣势了因为哈希表天生不关心元素之间的顺序和相对位置。这四道题的递进关系恰好印证了这一点454 是不同数组间配对383 是存在性与计数这两道题里元素之间没有顺序干扰哈希表用起来非常顺手。到了 15 和 18要求在同一个数组内选元素顺序和去重一下子变成核心矛盾哈希表处理起来就会非常拧巴。1.2 四道题的隐藏递进关系我整理了一张表把这四道题的差异列清楚题号核心问题数据来源是否涉及去重推荐解法454四组中各取一个数和为0的元组个数四个独立数组否哈希表分组383magazine能否拼出ransomNote两个字符串否数组哈希15一个数组中和为0的不重复三元组同一数组是排序双指针18一个数组中和为target的不重复四元组同一数组是排序双指针从 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)对得到同一个和比如ab 1出现 3 次那么每一个cd -1都能和这 3 组配对答案要累加 3所以必须记次数不能只记存在性。2.2 一趟填表一趟查表具体代码class Solution { public: int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) { unordered_mapint, 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底层实现连续内存哈希桶链表/红黑树内存占用固定 26 个 int动态分配每个节点有额外指针开销查找速度O(1) 直接寻址O(1) 但需计算哈希并处理冲突冲突问题无可能冲突退化时 O(n)调试难度直观可直接打出来看相对抽象很多人刷题时习惯性用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: 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) { 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[i1]相等时nums[i1]是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: 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 (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体会为什么这两个题要切换到双指针。刷完之后自己拿张纸画一下每道题的数据来源和去重需求你会发现这四道题刚好覆盖了两种思路的完整光谱。这四道题对我的最大价值其实是逼我理解了哈希表不是万能的这个结论。遇到组合类去重问题双指针往往比哈希表更优雅遇到配对计数问题哈希表又比双指针自然得多。能分清这两类场景比多背十道模板题都管用。