代码随想录算法训练营到第六天哈希表这章算是真正进入状态了。part01里我们刚学会用数组、Set、Map三种结构做查找解题思路基本还停留在“查一个东西在不在”的阶段。到了part02四数相加II、赎金信、三数之和、四数之和直接排着队上来难度一下从“会用”跳到了“会选、会拆、会放弃”。这篇文章把这四道题背后的拆解思路、去重细节和剪枝陷阱完整梳理一遍正在刷题或者准备面试的同学可以直接对着练。1. 哈希表part02不是“更多容器”而是把容器放进复杂问题里1.1 part01结束之后你对哈希表应该形成的三个基本判断part01里我们做了几道入门题有效的字母异位词、两个数组的交集、快乐数、两数之和。表面上看是在练题实际上是在建立三个基本判断第一数据范围连续且有限时数组就是最高效的哈希表。比如字符只可能出现在a到z之间那开一个长度为26的数组比用unordered_map还快。第二只查“存不存在”不考虑重复次数时用Set。两个数组的交集本质就是一个“去重后是否存在”的问题。第三既要查得看键又要统计出现次数用Map。两数之和里每个数只能配对一个答案但哈希表里存的是“值到下标”的映射所以用Map。这三个判断看起来简单但part02的每一道题都在逼你重新审视它们数组哈希还能不能继续用Map统计次数时要注意什么当哈希表本身处理不了“去重”时是不是该换一个思路这才是第六天的核心价值。1.2 part02四道题每一道都在练一种具体能力我先剧透一下接下来要讲的四题题目表面考点实际练的能力四数相加II哈希表统计和的出现次数分组降维把高维暴力拆成两个低维过程赎金信字符计数数组哈希的边界条件和“谁统计谁扣减”的方向问题三数之和找三元组哈希表解决不了的“去重”需要换排序双指针四数之和找四元组在三数之和外面再套一层循环剪枝条件要防负数所以part02的重点根本不是“再学更多容器”而是学会判断“这个场景下哈希表到底是不是最优解”。有些题用哈希表是锦上添花有些题用哈希表是自找麻烦。这个判断能力刷题量和面试表现的分水岭就在这里。2. 四数相加II把O(n^4)暴力拆成两个O(n^2)2.1 题目回顾与暴力复杂度分析题目是LeetCode 454给定四个整数数组nums1、nums2、nums3、nums4长度都是n从每个数组各取一个数问有多少个四元组满足四个数之和等于0。一个最容易想到的办法是四层循环for (int a : nums1) for (int b : nums2) for (int c : nums3) for (int d : nums4) if (a b c d 0) count;四层循环的时间复杂度是O(n^4)。n小的时候还没感觉一旦n到了200、500这个复杂度直接爆炸。刷题训练营里讲哈希表核心就是让你理解“用空间换时间”。这里同样适用能不能把某几层循环的结果先存起来让后续查询变快。2.2 分组查Map的推导过程把四个数拆成两组A组就是a b的所有结果B组就是c d的所有结果。原问题“abcd0”就等价于“ab -(cd)”。所以思路变成两步第一步遍历nums1和nums2把a b的所有结果放进一个哈希表键是和值是这个和出现了多少次。第二步遍历nums3和nums4对每一个c d的结果去哈希表里查“-(cd)”出现了多少次累加起来。核心代码如下#include unordered_map using namespace std; int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) { unordered_mapint, int sumCount; for (int a : nums1) { for (int b : nums2) { sumCount[a b]; } } int result 0; for (int c : nums3) { for (int d : nums4) { int target -c - d; auto it sumCount.find(target); if (it ! sumCount.end()) { result it-second; } } } return result; }时间复杂度从O(n^4)降到了O(n^2)代价是多了一个最多能存n^2个键值对的哈希表。这就是典型的空间换时间。Java版本用getOrDefault会更整洁int result 0; result sumCount.getOrDefault(-c - d, 0);Python可以直接用defaultdict或者Counter逻辑完全一样。2.3 为什么Map里存的是次数而不是布尔值这里有一个非常容易忽略的细节为什么Map的value是出现次数而不是true / false因为不同位置的组合可能得到同一个和。举个例子nums1[0] nums2[0] 3nums1[1] nums2[1] 3这两个结果的值虽然是同一个键3但它们来自不同的下标组合。当我们在nums3、nums4里找到了一个“-(cd) 3”时两组不同下标组合的a b都应该算作不同的四元组。如果Map里只存“3出现过没有”那这个答案就会少算一组。所以这里的规则是只要题目统计的是“元组个数”并且不同下标组合可能产生相同值哈希表的value就必须存次数。这个规则同样适用于后面其他需要统计数量的题目。还有一个编码细节。C里做c d时如果测试数据里有比较大的数建议用long long做计算和存储防止int溢出。LeetCode这道题的数据范围虽然一般不会溢出但养成这个习惯没有坏处。3. 赎金信数组哈希表的“计数题”顺序搞反就白写3.1 谁统计谁扣减思路方向最容易被绕进去题目是LeetCode 383给定两个字符串ransomNote和magazine判断ransomNote能不能由magazine里面的字符构成。注意magazine里的每个字符只能用一次。这题的关键是什么magazine是“资源方”ransomNote是“需求方”。我们要判断资源能不能满足需求。正确的做法是先遍历magazine统计每个字符出现的次数存进一个长度为26的数组。再遍历ransomNote每遇到一个字符就把对应位置的计数减一。一旦出现某个计数变成负数说明magazine里的字符不够用直接返回false。bool canConstruct(string ransomNote, string magazine) { int cnt[26] {0}; for (char c : magazine) { cnt[c - a]; } for (char c : ransomNote) { cnt[c - a]--; if (cnt[c - a] 0) { return false; } } return true; }很多刚练到这里的同学容易反过来先统计ransomNote再用magazine去减。这样得到的语义完全相反检查出来的就是“magazine能不能由ransomNote构成”了题目方向直接搞反。我的经验是写代码之前先在注释里写上“magazine是资源ransomNote是消耗”再开始动手。3.2 为什么字符有限时数组比Map更好用这道题完全可以只用unordered_map来做unordered_mapchar, int map; for (char c : magazine) map[c];但代码随想录训练营里对这题的定位是“数组哈希表”的经典应用。因为题目明确说明字符串只包含小写字母a到z一共26个字符这是连续且有界的键空间。此时直接用int cnt[26]就是最优哈希表查询一个字符的次数是O(1)直接用下标访问不需要计算哈希值。不需要处理冲突。空间比Map少很多。Map在键空间大、稀疏、不连续时才值得使用。比如字符集扩展到Unicode全量字符那开数组就不现实这时候用Map才合适。所以这道题虽然在训练营里是“小题”但它逼你想清楚一个核心问题你选哈希表的具体实现时依据是什么。答案是数据范围。3.3 与242有效的字母异位词放在一起看差别立刻清晰242题是判断两个字符串是不是字母异位词383题是判断一个字符串能否被另一个字符串覆盖。两题结构很像但252题的要求是“每个字符出现次数完全相等”383题只需要“magazine的每个字符次数大于等于ransomNote的次数”。写成代码时242的思路是先统计s再用t去减最后检查数组里有没有非零值383的思路是遍历magazine时计数遍历ransomNote时递减出现负数就提前返回false。这里的差异不是代码层面的复杂而是**“相等关系”和“包含关系”在计数上的不同表达**。把这两题放在同一天做比单刷十道同类型题更有效。这也是训练营安排part01和part02顺序的巧妙之处。4. 三数之和哈希表能做到但去重把一切毁了4.1 先说说“用哈希表硬解”为什么做而无功题目是LeetCode 15给定一个数组nums找出所有三元组满足三数之和为0并且三元组不能重复。如果你还按两数之和的思路想先固定一个数a再用哈希表找b c -a代码确实能写出来但落到“三元组不能重复”这个限制时就会非常痛苦。为什么痛苦哈希表擅长判断“存在性”但不擅长控制“唯一性”。同一个值可能出现在数组的不同位置你找到一组[-1, 0, 1]之后下一个位置又出现了[-1, 0, 1]这在数值上完全重复但哈希表并不知道只能靠一套很繁琐的去重逻辑先排序再用Set存三元组最后再把Set转回结果列表。这种做法在LeetCode上能通过吗有的用例能但很多用例会超时。因为Set去重需要额外的排序和哈希计算本来O(n^2)的算法会带上一个很重的常数。而且写起来非常绕要在存进Set之前对三元组排序要用字符串或者tuple当键还要记得在固定a时跳过重复值……我第一遍硬写哈希表版本时代码快到70行逻辑一复杂就漏了好几种重复情况。所以三数之和的正确姿势是放弃哈希表改用排序双指针。这是“会弃”的典型体现不是哈希表不好是这个问题用双指针天然更合适。4.2 排序双指针的完整流程先说一个基础前提三数之和要求返回三元组的值而不是下标。所以可以先对数组排序排序不会影响答案的正确性。排序之后整个数组是单调递增的。我们固定第一个数nums[i]然后用left指针指向i1right指针指向数组末尾通过移动left和right来逼近目标值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; // 排序后第一个数大于0后面不可能和为0 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; }为什么双指针能成立因为数组排序后left往右移动三数和会变大right往左移动三数和会变小。通过不断比较当前和与0的关系我们可以在O(n)内固定一个i时完成搜索。外层i遍历一次整体就是O(n^2)比四数相加II多一层的原因是这里要在同一个数组里选三个不同位置的值无法直接分组。4.3 三个去重细节错误点各不相同去重是三数之和最容易翻车的地方至少有三个细节要单独抠。细节一外层去重判断条件必须写nums[i] nums[i - 1]不能写成nums[i] nums[i 1]。为什么nums[i] nums[i 1]跳过的是“当前值等于下一个值”的情况这个条件会在i还没处理到的时候就直接跳过导致漏解。举个实际看到的错误数组是[-1, -1, 2]正确的三元组是[-1, -1, 2]如果用了nums[i] nums[i 1]在i0时就会因为nums[0] nums[1]把i0跳过正确答案直接没了。细节二找到一组答案后left和right都要跳过重复值然后各移动一步。很多第一次写的人只跳过了left侧的重复忘了right侧或者只移动一个指针。结果就是重复组合被反复添加最后发现有大量重复三元组。细节三外层剪枝条件nums[i] 0只能在“和为0”的题目里放心用如果target换了剪枝条件要重新想。这就是为什么三数之和看起来不难但真正手写通过率并不高。去重条件每一个都是从实际错误案例里总结出来的不是背下来就完事需要理解它到底在去掉什么。5. 四数之和在三数外面再套一层剪枝必须防负数5.1 从三数到四数结构只多了一层循环题目是LeetCode 18给定数组nums和目标值target找出所有四元组和等于target不能重复。有了三数之和的经验四数之和的框架非常容易理解排序之后外面套两层固定循环i和j内部再用left和right双指针。整体时间复杂度从O(n^2)变成O(n^3)。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 (i 0 nums[i] nums[i - 1]) continue; for (int j i 1; j n - 2; j) { 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; }这里的关键变化是两层去重i层去重和j层去重。i层和三数之和一样判断nums[i] nums[i - 1]即可。j层的判断条件是j i 1 nums[j] nums[j - 1]注意j的起点是i1所以j要保证在i1之后才进行“和前一位比较”的去重。我见过不少人在j层去重时会把条件写成j 0 nums[j] nums[j - 1]看起来差不多但问题在于第一次进入ji1时nums[j]本来就可能等于nums[i]这不是重复组合的根源而是合法组合的一部分不能跳过。正确写法里j i 1这个条件就是为了保护第一轮j。5.2 target是负数时剪枝条件要加“非负判断”四数之和和三数之和最大的区别除了多一层循环就是target不一定等于0。很多人会把三数之和里的nums[i] 0直接搬过来写成if (nums[i] target) break;这在target是正数时大概率没问题但target是负数时直接翻车。举个例子nums [-5, -4, -3, -2, 1]target -8。排序后nums[0] -5。如果你在i0处理完之后进入i1此时nums[1] -4。nums[1] target成立因为-4 -8。但你能break吗不能。因为后面还有-3和-2-4 -2 -1 -1组合可以等于-8。固定i1、j2、left3、right4时和正好是-8。提前break就直接漏解了。所以正确的剪枝写法要同时考虑当前数和target的大小关系以及当前数是否为非负数if (nums[i] target nums[i] 0) break;或者更严谨一点判断“当前固定值和后续最小几个值的和”是否已经大于targetif ((long long)nums[i] nums[i1] nums[i2] nums[i3] target) break;这个剪枝在排序数组里是安全的。理解了这一点就明白为什么不能照着三数之和硬抄条件。5.3 边界检查长度不够和int溢出四数之和还有几个边界问题容易踩。长度不足数组长度小于4时直接返回空结果。对应代码里最外层的n 4判断。int溢出数组里的数可能是10^9级别四个数相加很容易超过int范围。所以计算sum时我习惯用long long临时转换避免溢出导致的负数误判。LeetCode的用例现在很全不处理溢出这道题基本过不了。如果面试时遇到“k数之和”规律就是同一个数组内找k个数等于target排序双指针的方案需要(k-2)层外层循环里面套一个双指针。k3时是1层循环加双指针k4时是2层循环加双指针k5、6继续往上套。这个规律比硬背每道题的代码有用得多。6. 训练营第六天复盘哈希表的四种战场6.1 四道题的横向对比把part02的四道题放在一起看就能很清楚地感受到哈希表在不同场景下的边界题目数据来源核心方案时间复杂度核心难点四数相加II四个独立数组unordered_map统计和O(n^2)分组降维Map存次数赎金信两个字符串int[26]数组O(mn)统计方向数组vs Map选型三数之和同一个数组排序双指针O(n^2)三处去重细节四数之和同一个数组排序双指针O(n^3)双层去重、负数剪枝、int溢出四数相加II能放心用哈希表因为它面对的是四个独立数组不存在“同一个位置重复使用”的问题去重压力小Map天然能处理不同位置的相同值。三数之和、四数之和就不同了要在同一个数组里挑不重复的组合哈希表的“存在性判断”反而拖了后腿排序双指针成了更好的选择。这就是“选结构”的核心判断依据。6.2 我建议的三遍刷题法尤其适合哈希表part02这三道题尤其是三数之和和四数之和我强烈建议用“三遍刷题法”处理不要一遍写完就对答案。第一遍不看题解硬写。卡住也没关系记下你卡在哪里。比如三数之和你可能卡在去重条件或者在找完一组后不会移动指针。把卡点写下来比一次性看懂答案更有价值。第二遍对照题解总结规律后关掉题解默写代码。这一步你会发现很多“以为自己懂”的地方出问题比如j层去重的保护条件比如负数target下的剪枝写法。默写的时候卡住的每一个点都是你真实的薄弱点。第三遍隔两天重写一遍。这次要求自己能说清楚每个条件的含义为什么外循环去重是nums[i] nums[i-1]而不是nums[i] nums[i1]为什么四数之和的剪枝要加nums[i] 0说得清楚了才算真正吃透。这个方法的效果比连续刷十道类似题更好。因为每道题的“坑点”不同重写过程中的每一处卡壳都在强化正确的思考路径。6.3 哈希表在后续题目里还会怎么出现哈希表不是只在“和/差/交集”类题目里出现。后面做字符串、链表、二叉树、回溯、贪心时它还会以各种形态出现字符频次统计、元素是否访问过、映射关系缓存、状态枚举去重……到时候你会发现part02学到的“选结构”和“会放弃”的经验比记住几道题本身更重要。这个阶段的核心成长是建立起一套判断逻辑先看数据范围再看来源集合最后看是否需要去重。数据范围连续有限用数组集合大且稀疏用Map只关心存在性用Set需要唯一组合时认真考虑双指针和排序方案。能把这套判断逻辑跑通哈希表这一章就算真正过关了。我在实际训练中最大的感受是四道题刷完的那天晚上可能觉得“不过如此”但等到隔天回头重写四数之和时才发现自己还是会在j层去重和负数剪枝上犹豫。这种犹豫就是正常的不要怀疑自己不够聪明把它当成需要刻意练习的点再写一遍就好。