哈希表刷题避坑指南：从242到18题掌握核心套路

哈希表的坑我替你们踩完了，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，数组值是value；unordered_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 这六道题的难度梯度和考点分布

这六道题从易到难，正好覆盖哈希表的几个典型场景：

如果只看前四题，结论很清晰：哈希表最常见的使用场景就是“用一个map把之前出现过的信息存起来，然后遍历到新元素时去map里找配对”。这个套路一定要形成肌肉记忆，后面做很多题都会用到。

但要注意，15和18虽然也在哈希表标签下，它们的标准解法却是排序+双指针。原因后面第四节详细说，这里先记住一个方向：涉及“返回不重复解”的多重循环求和问题，优先考虑排序+双指针，而不是哈希。

2. 前四题：哈希表直接应用的四个样板

2.1 242题：把数组当哈希表用

题目很简单：判断s和t是否为字母异位词（字母相同但排列不同）。比如s = "anagram"，t = "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; vector<int> 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的遍历：

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { unordered_set<int> set1(nums1.begin(), nums1.end()); vector<int> 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。

vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, 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都存进map，map里key=3对应的value只能保留一个下标，那正确答案就丢了。先查后存，能保证key当前对应的value是“之前遍历过的最近一个下标”，不会覆盖还没遇到的信息。

还有一个容易踩的坑：map的key存的是nums[i]的值，value存的是下标i。有人图省事用map<int, int>（底层红黑树）代替unordered_map，这题数据量不大时两种都能过，但如果面试时数据规模是10⁵甚至更大，红黑树的O(log n)查找在常数上就吃了亏，该用unordered_map的地方不要犹豫。

2.4 454题：四数相加II的分组思想

四个数组A、B、C、D，每个数组取一个数，四数之和为0，问有多少种组合。暴力的O(n⁴)是必挂的，所以得有巧劲。

核心思路是分组：先把A和B的所有组合和存进map，key是a + b的值，value是这个和出现的次数；再遍历C和D的所有组合，查找-(c + d)在map中出现的次数，累加到结果里。这样复杂度从O(n⁴)降到O(n²)。

int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map<int, 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]，那a+b = 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 三数之和的去重细节

先看整体代码结构：

vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> 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[i+1]”。因为i-1是已经处理过的位置，跳过可以让i每次停留在相同元素的第一个；如果判断i+1，会直接跳过i作为a的合法解，比如[-1,-1,2]这个三元组就丢了。二是找到一组解后，left和right都要跳过重复元素，避免产生重复三元组。三是left和right在去重后必须再各自移动一步，否则指针不动会陷入死循环。

一开始我按“nums[i] == nums[i+1]”写，跑用例时发现在[-1,-1,2]这种样例会丢解，调试半天才意识到是去重位置写错了。这个错误很典型，值得记下来。

3.3 四数之和的剪枝优化

四数之和是“找出所有和为target的四元组”，和三数之和思路完全一致，区别是外面多套一层循环。固定前两个数a和b，然后双指针找c和d。时间复杂度O(n³)。

vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> 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[i+1] + nums[i+2] + nums[i+3] > 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[j+1] + nums[j+2] > 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 六道题的时间空间复杂度速查

注意看15和18的空间复杂度是O(1)，这里计算的是算法本身除了结果数组之外需要的额外空间。这跟哈希表的O(n)空间形成鲜明对比，也是双指针解法更优的一个重要原因——时间复杂度相同的情况下，空间更省。

4.2 刷题中常见的六个问题

我把自己刷这套题时踩过的坑和总结的经验整理成了一张速查表，碰到异常表现可以直接对照排查：

4.3 面试时回答这类题目的正确姿势

如果面试官让你写三数之和，不要闷头就开始敲代码，先主动说思路：这题有两个难点，一是如何在O(n²)内完成查找，二是如何保证结果不重复。我的方案是先排序，固定第一个数，用双指针在剩余区间内搜索，去重通过跳过相邻重复元素实现。这样做的好处是：排序让重复元素聚拢，去重逻辑变得极其简单。

两数之和和四数相加II这类“只需要计数或一对下标”的题，优先考虑哈希表；三数之和和四数之和这类“需要列出所有不重复解”的题，优先考虑排序+双指针。判断标准就一条：解集合是否要求唯一性。只要出现“不重复”三个字，哈希表的路基本就堵死了一半。

我在实际刷题中还有一个心得：写完代码后，自己拿几个典型用例在纸上跑一遍。242题拿s="anagram"和t="nagaram"跑一遍；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”，两者本质是同一个东西，只是使用场景不同。这一层打通之后，后面遇到任何“是否存在”类问题都能在脑子里自动映射到合适的哈希方案。

这套题建议至少刷两遍。第一遍只看思路和代码，把每道题的考点和易错点记录一遍；第二遍合上书自己写，写完对照标准解法，重点检查去重逻辑和边界条件。两遍下来，哈希表这个知识点基本就能稳住了。