哈希表的坑我替你们踩完了242、349、1、454、15、18这六道题从入门到进阶正好串起哈希表的完整用法。我翻了不少题解结合自己刷题时的理解和调试过程整理成这套笔记按“能用数组就别用map、能用unordered就别用map、去重想清楚到底谁去重”这三个原则来拆解看完你也能get到哈希表的核心套路。先说清楚这套题的价值。LeetCode上哈希表标签的题有上百道但大多数题的精髓都集中在“如何设计key”、“何时用数组替代哈希表”、“如何在O(1)时间内判断元素存在”这几点。242、349、1、454这四道是纯哈希表题分别对应数组哈希、set去重、map一遍遍历、分组哈希而15和18则是经典的双指针题表面上是“看到sum就想哈希”实际上用哈希做反而会绕进死胡同。这六道一起刷能让你彻底搞明白“数据结构的选型是依题而定的”而不是看到哈希标签就无脑上unordered_map。废话不多说直接进入正题。1. 哈希表刷题前的三个认知1.1 哈希表到底是干嘛的哈希表的核心功能就一句话在O(1)时间内完成“某个值是否存在”的查询。数组可以看作一个天然的哈希表下标是key数组值是valueunordered_map则是更通用的哈希表key可以是任意可哈希类型value可以是任意类型unordered_set则是只关心“有没有”不关心“有几个”、“对应谁”。判断一道题该不该用哈希就看两个条件一是有没有“查找”需求二是查找的次数多不多、数据规模大不大。242题里要比较两个字符串的字符构成查找26个字母的出现次数349题要判断某个数在另一个数组里是否存在1题要判断“target - num”是否已经在遍历过程中出现过454题要判断“-(c d)”在前面有没有出现过。这些都是典型的“查询是否存在”场景哈希表就是为这些场景设计的。刷哈希表题最关键的一步不是写代码而是先判断数据范围和类型。如果key的范围是固定的、有限的比如小写字母只有26个、ASCII码只有128个、数字范围只有几万直接用数组如果key是字符串、自定义结构体、范围不确定的整数才考虑unordered_map / unordered_set。1.2 这六道题的难度梯度和考点分布这六道题从易到难正好覆盖哈希表的几个典型场景题目核心考点数据结构易错点242 有效的字母异位词数组哈希计数vector (26)忘记初始化为0349 两个数组的交集set去重查找unordered_set输出结果去重1 两数之和一遍哈希查找unordered_map先查后放防止重复用自身454 四数相加II分组哈希unordered_map两两组合空间换时间15 三数之和排序双指针去重数组三层循环去重逻辑18 四数之和排序双指针剪枝数组剪枝条件要分正负数讨论如果只看前四题结论很清晰哈希表最常见的使用场景就是“用一个map把之前出现过的信息存起来然后遍历到新元素时去map里找配对”。这个套路一定要形成肌肉记忆后面做很多题都会用到。但要注意15和18虽然也在哈希表标签下它们的标准解法却是排序双指针。原因后面第四节详细说这里先记住一个方向涉及“返回不重复解”的多重循环求和问题优先考虑排序双指针而不是哈希。2. 前四题哈希表直接应用的四个样板2.1 242题把数组当哈希表用题目很简单判断s和t是否为字母异位词字母相同但排列不同。比如s anagramt nagaram返回true。我第一遍做的时候直接用的unordered_map遍历s往map里遍历t往map里--最后检查所有value是否都为0。这个解法没问题但不够好。因为题目明确说了“字符串只包含小写字母”这意味着key的取值范围被锁死在26个字母里数组完全够用而且更快、更省空间。bool isAnagram(string s, string t) { if (s.size() ! t.size()) return false; vectorint count(26, 0); for (char c : s) count[c - a]; for (char c : t) { count[c - a]--; if (count[c - a] 0) return false; } return true; }这里有个实用小技巧不用遍历完再检查所有count是否为0直接在第二个循环里边减边检查一旦出现负数就说明t里有s没有的字符直接返回false。这样平均情况下能省掉最后一次遍历的耗时。时间复杂度O(n)空间复杂度O(1)——因为数组长度固定为26。如果用unordered_map空间复杂度虽然也是O(1)最多26个键值对但常数项大得多哈希函数的计算开销、内存分配的耗时在小数据量下反而更慢。能用定长数组解决的问题绝不引入哈希函数。2.2 349题set在去重场景下的正确姿势两个数组的交集输出结果中的每个元素唯一。比如nums1 [4,9,5]nums2 [9,4,9,8,4]输出[9,4]或[4,9]都可以。暴力做法是两层循环遍历O(n * m)的复杂度大概率超时。熟悉哈希表的话马上就能想到先把nums1的所有元素放进一个set然后遍历nums2如果元素在set里出现就是交集元素。但这里有个问题nums2里可能有重复元素比如上面的例子里9和4各出现两次如果直接输出结果就会有重复。解决思路有两种一是用结果set去重先存进unordered_set最后再转成vector二是输出一个元素后立即从查找set里删掉它这样后面再遇到就不会重复输出。我倾向于第二种因为少一次set转vector的遍历vectorint intersection(vectorint nums1, vectorint nums2) { unordered_setint set1(nums1.begin(), nums1.end()); vectorint res; for (int num : nums2) { if (set1.count(num)) { res.push_back(num); set1.erase(num); // 关键输出后删除避免重复 } } return res; }为什么用unordered_set而不是set因为这里只关心“在不在”不关心顺序。set底层是红黑树插入和查找都是O(log n)unordered_set底层是哈希表平均O(1)。除非题目要求输出结果有序否则一律优先unordered_set。2.3 第1题两数之和map一遍遍历的完整套路这题是LeetCode的“Hello World”几乎所有人入坑算法刷题都是从这里开始的。题目给定数组nums和一个目标值target找出和为target的两个数返回它们的下标。暴力解法两层循环O(n²)。用哈希表可以把时间复杂度降到O(n)思路是遍历数组时检查target - nums[i]是否已经在map里出现过如果出现过答案就是map里的value和当前下标i如果没有把nums[i]和下标i存进map。vectorint twoSum(vectorint nums, int target) { unordered_mapint, int indexMap; for (int i 0; i nums.size(); i) { int remain target - nums[i]; if (indexMap.count(remain)) { return {indexMap[remain], i}; } indexMap[nums[i]] i; } return {}; }这段代码的核心细节在于“先查后存”。为什么不能先把所有元素存进map再统一查因为数组里可能有重复值比如nums [3, 3]target 6如果先把两个3都存进mapmap里key3对应的value只能保留一个下标那正确答案就丢了。先查后存能保证key当前对应的value是“之前遍历过的最近一个下标”不会覆盖还没遇到的信息。还有一个容易踩的坑map的key存的是nums[i]的值value存的是下标i。有人图省事用mapint, int底层红黑树代替unordered_map这题数据量不大时两种都能过但如果面试时数据规模是10⁵甚至更大红黑树的O(log n)查找在常数上就吃了亏该用unordered_map的地方不要犹豫。2.4 454题四数相加II的分组思想四个数组A、B、C、D每个数组取一个数四数之和为0问有多少种组合。暴力的O(n⁴)是必挂的所以得有巧劲。核心思路是分组先把A和B的所有组合和存进mapkey是a b的值value是这个和出现的次数再遍历C和D的所有组合查找-(c d)在map中出现的次数累加到结果里。这样复杂度从O(n⁴)降到O(n²)。int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) { unordered_mapint, int sumAB; for (int a : nums1) { for (int b : nums2) { sumAB[a b]; } } int count 0; for (int c : nums3) { for (int d : nums4) { int target -(c d); if (sumAB.count(target)) { count sumAB[target]; } } } return count; }这题我认为是前四题里含金量最高的一道因为它展示了哈希表题的一个核心优化思路减少维度的关键不是靠多聪明的循环而是靠一次分组把四维问题转成两个二维问题。这种分治思想在后面的K-sum问题里也会用到。有个细节要注意map的value累加的是次数不是简单的布尔存在。比如A[1,1]B[-1,-1]那ab 0出现了4次结果必须是4如果value只是1就错了。这也是为什么要用map而不是set的原因。3. 15题和18题排序双指针的经典递进3.1 为什么三数之和、四数之和不用哈希解法三数之和的经典问法是“找出所有和为0且不重复的三元组”。题目最后一个限定词“不重复”是整个题目的灵魂也是哈希做法的死穴。哈希思路能做吗能。固定一个数a然后在剩余元素中用类似两数之和的哈希方法找b和c。但问题来了哈希方法找出来的b和c可能有序但结果中的三元组仍然重复比如[-1,0,1]和[1,0,-1]实际是同一组解哈希方法无法轻易去重。要手动处理这些重复情况代码会非常臃肿逻辑也容易绕晕。所以标准解法换成排序双指针先排序让数组有序然后固定一个数a用左右指针在a右边寻找b和c。因为数组有序指针可以根据和的大小智能移动去重也变得非常自然——跳过相邻的相同元素即可。这也是“数据结构不适用时果断换思路”的典型案例。3.2 三数之和的去重细节先看整体代码结构vectorvectorint threeSum(vectorint nums) { vectorvectorint res; sort(nums.begin(), nums.end()); int n nums.size(); for (int i 0; i n - 2; i) { 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) { res.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 res; }去重要注意三点一是外层i的去重判断条件是“nums[i] nums[i-1]”而不是“nums[i] nums[i1]”。因为i-1是已经处理过的位置跳过可以让i每次停留在相同元素的第一个如果判断i1会直接跳过i作为a的合法解比如[-1,-1,2]这个三元组就丢了。二是找到一组解后left和right都要跳过重复元素避免产生重复三元组。三是left和right在去重后必须再各自移动一步否则指针不动会陷入死循环。一开始我按“nums[i] nums[i1]”写跑用例时发现在[-1,-1,2]这种样例会丢解调试半天才意识到是去重位置写错了。这个错误很典型值得记下来。3.3 四数之和的剪枝优化四数之和是“找出所有和为target的四元组”和三数之和思路完全一致区别是外面多套一层循环。固定前两个数a和b然后双指针找c和d。时间复杂度O(n³)。vectorvectorint fourSum(vectorint nums, int target) { vectorvectorint res; 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; if ((long long)nums[i] nums[i1] nums[i2] nums[i3] target) break; if ((long long)nums[i] nums[n-1] nums[n-2] nums[n-3] target) continue; for (int j i 1; j n - 2; j) { if (j i 1 nums[j] nums[j - 1]) continue; if ((long long)nums[i] nums[j] nums[j1] nums[j2] target) break; if ((long long)nums[i] nums[j] nums[n-1] nums[n-2] target) 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) { res.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 res; }这题针对性提出两个剪枝一是在固定i后如果最小的四个数之和已经大于target那后面更大的一组数不可能满足条件直接break如果i加上最大的三个数还小于target那这个i太小了直接continue到下一个i这种写法能明显减少无效循环。二是需要把sum转成long long因为LeetCode的测试数据里四个数相加可能溢出int范围。转类型这个细节不处理跑大数据时会出现完全摸不着头脑的错误答案。这里最让我感慨的是“同样套路在不同难度下的扩展”。把三数之和的思路吃透四数之和其实只多了剪枝和类型转换两个考点。K数之和的通用解法就是“排序固定前K-2个数双指针”规律性非常强。4. 复杂度对比与实战排查指南4.1 六道题的时间空间复杂度速查题号题目名称核心方法时间复杂度空间复杂度242有效的字母异位词数组计数O(n)O(1)349两个数组的交集unordered_setO(nm)O(min(n,m))1两数之和unordered_mapO(n)O(n)454四数相加II分组unordered_mapO(n²)O(n²)15三数之和排序双指针O(n²)O(1)18四数之和排序双指针O(n³)O(1)注意看15和18的空间复杂度是O(1)这里计算的是算法本身除了结果数组之外需要的额外空间。这跟哈希表的O(n)空间形成鲜明对比也是双指针解法更优的一个重要原因——时间复杂度相同的情况下空间更省。4.2 刷题中常见的六个问题我把自己刷这套题时踩过的坑和总结的经验整理成了一张速查表碰到异常表现可以直接对照排查异常表现可能原因解决方案用数组哈希时结果全错数组长度不够或忘了初始化用vector (26, 0)代替int count[26]这种写法后者在函数内不会自动清零349题输出结果有重复忘记在输出后删掉set里的元素输出后立即set1.erase(num)两数之和返回的答案里有相同下标先存后查而不是先查后存调整为先查后存就永远不会用到当前元素自身454题计数错误map的value没累加次数而是赋了1value表示出现次数用sumAB[ab]而不是1三数之和丢解外层去重条件写成了nums[i]nums[i1]改为nums[i]nums[i-1]避免跳过合法组合起点四数之和结果溢出int相加超出范围(long long)强制转换后再相加4.3 面试时回答这类题目的正确姿势如果面试官让你写三数之和不要闷头就开始敲代码先主动说思路这题有两个难点一是如何在O(n²)内完成查找二是如何保证结果不重复。我的方案是先排序固定第一个数用双指针在剩余区间内搜索去重通过跳过相邻重复元素实现。这样做的好处是排序让重复元素聚拢去重逻辑变得极其简单。两数之和和四数相加II这类“只需要计数或一对下标”的题优先考虑哈希表三数之和和四数之和这类“需要列出所有不重复解”的题优先考虑排序双指针。判断标准就一条解集合是否要求唯一性。只要出现“不重复”三个字哈希表的路基本就堵死了一半。我在实际刷题中还有一个心得写完代码后自己拿几个典型用例在纸上跑一遍。242题拿sanagram和tnagaram跑一遍349题拿带重复元素的[4,9,5]和[9,4,9,8,4]跑一遍三数之和拿[-1,0,1,2,-1,-4]跑一遍去重逻辑。纸上跑通后再提交到OJ基本一遍过。5. 这套题真正让我开窍的地方刷完这六道题我觉得最值钱的东西不是背住了某个模板而是建立了一套“遇到求和问题先想查找遇到去重问题先想排序”的直觉。242和349让我记住了“数据范围小就上数组”1和454让我理解了“map的价值在于记住历史”15和18让我学会了“当哈希表处理去重过于痛苦时果断换成双指针”。有一件事我在实战中发现特别有效把每一道题的关键代码片段摘出来放在一起对比。看一眼242的数组哈希再看一眼1的map哈希你会发现“数组就是下标有限且连续的map”两者本质是同一个东西只是使用场景不同。这一层打通之后后面遇到任何“是否存在”类问题都能在脑子里自动映射到合适的哈希方案。这套题建议至少刷两遍。第一遍只看思路和代码把每道题的考点和易错点记录一遍第二遍合上书自己写写完对照标准解法重点检查去重逻辑和边界条件。两遍下来哈希表这个知识点基本就能稳住了。