哈希表专题：数组、Set、Map怎么选？四道经典算法题讲透

代码随想录算法训练营第六天的打卡笔记来了。今天主题是哈希表，涉及四道经典题：242. 有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和。我正在二刷（二周目），一刷时很多题是“照猫画虎”写过去的，这次重新过一遍，明显有“终于通了”的感觉。如果你也准备刷算法，或者正在被哈希表绕晕，这篇笔记应该能帮你少走点弯路。

我自己把“吃饭香系列”理解为：学完一天的内容，脑子有实实在在的收获，吃饭都格外香。第六天正好进入哈希表专题，这个专题非常生活化——字典查字、按号找柜子、抽屉放东西，都是在用哈希的思想。只是换成代码表达之后，很多人会卡在“什么时候用数组、什么时候用Set、什么时候用Map”这个问题上。这篇我就结合今天这四道题，把这个问题一次说透。

1. 哈希表理论基础：先弄清楚数组、Set、Map到底怎么选

1.1 核心思想是“拿空间换时间”

哈希表解决的痛点只有一个：快速查找。在数组、链表这些结构里，找一个元素往往要遍历一遍，时间复杂度是O(n)。哈希表通过一个哈希函数，把“要查找的键”直接映射成“存储位置”，平均情况下一次定位就能拿到结果，时间复杂度O(1)。

我自己喜欢用一个比喻：去图书馆还书。如果书是按照编号直接放在固定位置的，你根据编号走过去就能拿到；如果所有书都堆在一个大桌子上，你得一本一本翻。哈希表就是给每本书提前分配好编号的书架。

不过“按编号放书”会带来一个问题：如果两本书的编号映射到了同一个位置怎么办？这就是哈希碰撞。常见的解决办法有两种：

• 链地址法：每个位置挂一个链表，碰撞的元素链在后面。Java的HashMap用的就是这种思路，哈希桶里是链表，链表太长时会转成红黑树优化。
• 开放地址法：如果目标位置被占了，就继续找下一个空位。ThreadLocal里的ThreadLocalMap用的就是开放地址法。

在实际做题时，我们通常不需要自己实现哈希表，语言自带的HashMap、HashSet、数组下标就够了，但理解碰撞机制有助于你判断为什么哈希表某些极端情况会退化到O(n)，比如HashMap在大量哈希碰撞时会退化，Java 8之后引入红黑树就是针对这种情况做的优化。

1.2 数组、Set、Map三者的使用场景对比

这是今天最重要的部分。刷哈希表专题，代码往往不复杂，真正的难点是第一步：拿到题目后，该用哪个结构？

我总结了一套判断逻辑，一刷时我经常靠猜，二刷后基本能稳定套用：

举个例子你就明白了。要统计一句话里每个英文字母出现的次数，字母只有26个，用int[26]就行，下标0代表a，下标25代表z。如果统计的是“数字0到1000之间每个数是否出现过”，那就开boolean[1001]，下标就是数字本身。只有当键的空间很大、不连续，比如字符串、对象、很大的整数时，才需要上HashMap。

强调一句：数组本身就是哈希表的一种实现，而且是性能最好的那种。很多题目能用数组就别绕到HashMap，代码更短、运行更快、也不会出现装箱拆箱的开销。

1.3 哈希表的复杂度与常见陷阱

平均情况下，哈希表的查找、插入、删除都是O(1)。这里的“平均”很重要，因为最坏情况（大量碰撞）会退化到O(n)。所以刷题时，题目如果没有出现“碰撞攻击”这种极端场景，按O(1)分析就好。

常见的两个陷阱：

• 用HashSet或HashMap时，如果要多次遍历或多次访问，尽量不要反复执行containsKey、contains这类查询后再插入，能合并到一次循环里就合并，减少无谓开销。
• 遍历HashMap/HashSet的输出顺序是不保证的。这个点尤其容易在“输出结果”上翻车：如果题目要求按升序输出，用普通HashSet去收集结果就不行，需要排序或改用TreeSet。今天的349题不要求顺序，所以直接Set没问题，但你要知道这个特性存在。

2. 242. 有效的字母异位词：用数组做哈希最简单

2.1 题目理解：异位词的本质是“字符频率相同”

题目给两个字符串s和t，问它们是不是字母异位词，比如s = "anagram"，t = "nagaram"，重排之后能完全对应，就返回true。

最直观的暴力做法是排序：把两个字符串都排好序，然后逐位比较。复杂度O(n log n)，能过，但这不是哈希表专题想要的解法。哈希思路很直接：统计s里每个字符出现的次数，再拿t的字符去抵消，如果最后所有次数都是0，说明两个字符串的字符组成完全一样。

这里有一个关键选择：用数组还是用Map？题目明确说了s和t只包含小写字母，那就是26个字符。用小写字母的ASCII码值减去'a'的ASCII码值，就能映射到0到25的下标。所以int[26]就是最合适的哈希表，既不需要计算复杂哈希值，也不需要处理哈希碰撞，直接用字符编码当下标，天然就是O(1)存取。

2.2 数组实现与完整代码

完整代码如下：

class Solution { public boolean isAnagram(String s, String t) { if (s.length() != t.length()) { return false; } int[] record = new int[26]; for (char c : s.toCharArray()) { record[c - 'a']++; } for (char c : t.toCharArray()) { record[c - 'a']--; } for (int count : record) { if (count != 0) { return false; } } return true; } }

代码逻辑分三步走：第一步，遍历s的每个字符，在record对应位置加一，相当于把s里出现的字母逐个数一遍；第二步，遍历t的每个字符，在record对应位置减一，相当于用t里的字母去抵消之前统计的次数；第三步，检查整个record数组，只要有一个位置不是0，就说明两个字符串的某个字符数量对不上，返回false。三步逻辑并不复杂，但每一步背后都有明确的意图：先积累频率，再消耗频率，最后验证是否有余额，这也是字符串统计类题目最常见的套路之一。

我手动模拟一下s = "anagram", t = "nagaram"：统计a出现3次，n出现1次，g出现1次，r出现1次，m出现1次。然后用t逐个抵消，最后record数组全部归零，返回true。如果t换成"nagaramx"，末尾多了一个x，长度判断就会直接把它拦下来，根本进不到下面的循环。

注意：第一步先判断两个字符串长度是否相等。如果长度不同，根本不可能互为异位词，直接返回false。这个判断看似可有可无，但在数据量大时能省掉后续很多无意义操作，而且逻辑上也更完整。很多人写这题会漏掉这个判断，虽然不影响最终结果，但没有提前剪枝显得不够严谨。

复杂度分析：时间复杂度O(n)，n是字符串长度，我们总共遍历了两遍字符串加一遍固定长度26的数组，可以认为O(n)。空间复杂度O(1)，因为无论输入多长，record数组大小固定为26。对比排序解法O(n log n)的时间和O(1)或O(n)的空间，数组哈希方案在时间上优势明显，而且实现也更简单。

2.3 这道题给我的两个启发

第一，不要一上来就HashMap。很多人在242题会写Map<Character, Integer>，功能上没错，但完全没有必要。数组下标天然就是字符编码，用数组不仅更简洁，还避免了HashMap的哈希计算和装箱开销。做算法题不是写业务代码，能用轻量结构就不要上重量级结构。

第二，这个题是后面很多字符串哈希题的“祖宗”。比如49题字母异位词分组，可以把每个单词的频率数组转成字符串作为key；438题找到字符串中所有字母异位词，要用滑动窗口加频率数组。242你能顺手写出数组版本，后面这些题会顺很多。如果这里你还在纠结Map的put和get，后面会写得很累。

3. 349. 两个数组的交集：去重比找重合更值得注意

3.1 题目分析：交集的三个基本要求

题目给两个数组nums1和nums2，要求返回它们的交集。注意三点：输出结果中每个元素唯一，不考虑顺序，也就是要去重；元素只要在两个数组中都出现过就算；结果长度、顺序都没有要求。

暴力做法是两层循环，外层遍历nums1，内层遍历nums2，找到相同元素就加入结果，最后再去重。时间复杂度O(n*m)，明显不划算。而且如果不小心把重复元素全加进结果，后面还得再做一次去重，代码更麻烦。

用哈希表的思路是这样：先把nums1的所有元素放进一个Set，再遍历nums2，每当遇到一个元素在Set里存在，就说明它是交集的一部分，加入结果Set去重，最后把结果Set转成数组返回。

为什么这里需要两个Set？第一个Set用于快速判断nums2的元素是否在nums1中出现过，第二个Set用于保证结果不重复。因为nums2里可能多次出现同一个元素，比如[2, 2, 2]，如果不加结果Set，2会被收集三次，最终输出就错了。

3.2 两个版本实现与细节对比

先看最通用的Set版本：

class Solution { public int[] intersection(int[] nums1, int[] nums2) { if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) { return new int[0]; } Set<Integer> set1 = new HashSet<>(); for (int num : nums1) { set1.add(num); } Set<Integer> resultSet = new HashSet<>(); for (int num : nums2) { if (set1.contains(num)) { resultSet.add(num); } } int[] res = new int[resultSet.size()]; int index = 0; for (int num : resultSet) { res[index++] = num; } return res; } }

这个实现的时间复杂度O(n+m)，空间复杂度O(n)。优点是简单，而且不依赖数据范围，任何整数都行。注意开头的空数组判断：如果两个数组任何一个为空，直接返回空数组，避免后面出现空指针问题。

再来看数组标记版本。题目其实给了线索：0 <= nums1[i], nums2[i] <= 1000。这意味着我们可以开一个boolean[1001]，下标就是数值本身：

class Solution { public int[] intersection(int[] nums1, int[] nums2) { boolean[] table = new boolean[1001]; for (int num : nums1) { table[num] = true; } List<Integer> list = new ArrayList<>(); for (int num : nums2) { if (table[num]) { list.add(num); table[num] = false; // 去重关键 } } int[] res = new int[list.size()]; for (int i = 0; i < list.size(); i++) { res[i] = list.get(i); } return res; } }

注意：数组标记版本里，把元素加入结果后一定要table[num] = false。否则nums2里有重复元素时，同一个数字会被收集多次。这个细节我在一刷时踩过坑，输出结果里全是重复值。手动跑一个例子：nums2 = [2, 2]，如果收集完第一个2后不把table[2]改成false，第二次遇到2时table[2]还是true，就会再把2加进list一次，最终结果变成[2, 2]，明显不符合“唯一”要求。

数组版本的时间复杂度还是O(n+m)，但空间上boolean数组大小固定1001，而且避免了HashSet的哈希计算和自动装箱，实际运行通常更快。缺点是强依赖题目给的数据范围，如果范围变成10^9，这个方案就废了，老老实实用Set。

3.3 事后的思考：到底哪个版本更好？

我的建议是：面试时能根据数据范围选方案，是非常加分的能力。你甚至可以主动问面试官：数组元素的范围有限制吗？如果有限制且不大，数组标记法是最优解；如果范围很大或者可以是任意整数，就用Set。这种“先确认约束，再设计算法”的习惯，比直接闷头写Set更能体现工程思维。

另外提一下Java里HashSet输出顺序的问题。上面Set版本最后把resultSet转成数组，遍历顺序不保证是插入顺序，也就是说返回的排序可能是[2, 1]而不是[1, 2]。不过这道题明确说“不考虑输出结果的顺序”，所以没有影响。如果题目要求升序输出，你需要改成先把结果排序，或者直接用TreeSet，或者在收集后手动排序。

4. 202. 快乐数：看似数学题，本质是链表环检测

4.1 快乐数的定义与核心矛盾

题目给一个正整数n，不断地让n等于它各位数字的平方和，如果这个过程最终能得到1，那n就是快乐数；如果陷入了一个不包含1的循环，就永远也到不了1。

比如19：1^2 + 9^2 = 82，8^2 + 2^2 = 68，6^2 + 8^2 = 100，1^2 + 0^2 + 0^2 = 1，所以19是快乐数。

关键问题是：如何判断“永远也到不了1”？你不可能真的无限循环下去。好消息是，非快乐数一定会在某个时刻进入一个循环，而不是无限增大。原因在于：对于一个多位数，各位数字平方和会很快变得很小。以三位数999为例，各位平方和是81 + 81 + 81 = 243，已经比999小很多；对更大的数，平方和与位数有关，但增长远慢于数值本身，所以最后一定会掉到某个有限范围内，然后就只能在这个范围内打转，要么到达1，要么进入循环。

4.2 Set判重解法与快慢指针解法

既然一定会出现循环，那问题就变成：如何检测循环？最直接的办法是用哈希表记录已经出现过的数字，也就是Set判重。

class Solution { public boolean isHappy(int n) { Set<Integer> seen = new HashSet<>(); while (n != 1 && !seen.contains(n)) { seen.add(n); n = getNext(n); } return n == 1; } private int getNext(int n) { int sum = 0; while (n > 0) { int d = n % 10; sum += d * d; n /= 10; } return sum; } }

我手动模拟n = 2：2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4，发现4已经出现过，于是跳出循环，返回false。这个测试用例是很好的检查点，如果代码写错，很可能在某个环节多算或少算一次。

还有一种不依赖额外空间的解法：快慢指针。把getNext当成一个指针移动的过程，慢指针每次走一步，快指针每次走两步，如果序列中存在环，两个指针一定会相遇。相遇后判断一下：如果当前值是1就返回true，否则返回false。这个思路和141题环形链表完全一样，只不过把链表节点换成了数字平方和。

class Solution { public boolean isHappy(int n) { int slow = n; int fast = getNext(n); while (fast != 1 && slow != fast) { slow = getNext(slow); fast = getNext(getNext(fast)); } return fast == 1; } private int getNext(int n) { int sum = 0; while (n > 0) { int d = n % 10; sum += d * d; n /= 10; } return sum; } }

复杂度方面，无论Set版本还是快慢指针版本，时间都约等于O(log n)，因为数字每经过一轮，位数都在快速减少。空间上，Set版本是O(log n)，快慢指针版本是O(1)。实际刷题中Set版本更容易理解和记忆，面试时先写Set版本，再提一句快慢指针能优化空间，会是很漂亮的加分点。

4.3 这个题对哈希表的训练点

202题最妙的点在于：哈希表在这里不是存“值出现了几次”，也不是存“值和下标的对应关系”，而是存“这个状态是否出现过”。一旦发现当前状态之前出现过，就可以判定进入了循环。

这种“用哈希表记录历史状态来防循环”的思想，在很多题目里都能看到。比如217题判断数组里是否存在重复元素，本质也是“出现过没有”的问题；再比如DFS里防止走回头路的visited数组，也是同一种思路。所以刷202题，别只把它当成一个数学小游戏，它其实是在练你“如何用哈希来做状态判重”。

5. 1. 两数之和：HashMap的经典教科书应用

5.1 从暴力到HashMap的思路演进

终于到了全网刷题量最高的那题：两数之和。题目给一个数组nums和一个目标值target，要求找出和为target的两个整数的下标，并且每个输入都恰好有一个答案，同一个元素不能重复使用。

最没技术含量的做法是暴力枚举：外层i从0到n-1，内层j从i+1到n-1，只要nums[i] + nums[j] == target就返回。时间复杂度O(n^2)，用是能用，但在大数据量下会超时。

优化思路其实很自然：当我们遍历到nums[i]时，真正关心的问题不是“后面还有哪些数”，而是“之前有没有出现过target - nums[i]这个数”。如果出现过，它的下标是多少？这不就是哈希表最擅长的“快速查找”吗？

于是就有了HashMap解法：key存数字的值，value存这个值在数组中出现的下标。遍历数组，每次都检查target - 当前值在不在map里，在就直接返回，不在就把当前值和下标放进map。

5.2 一次遍历的正确写法与关键细节

代码如下：

class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int[]{map.get(complement), i}; } map.put(nums[i], i); } return new int[0]; } }

这里有一个非常容易踩的坑：到底是先查再放，还是先放再查？

答案是必须先查再放。举个例子：nums = [3, 3]，target = 6。如果先放再查，遍历到第一个3时map是空的，查不到target - 3 = 3，于是放入map {3: 0}；遍历到第二个3时，map里已经有3: 0，于是返回[0, 0]。这就不对了，因为同一个元素被用了两次，而下标0和1才是正确答案。如果先查再放，遍历到第二个3时，先查map，发现里面有3: 0，返回[0, 1]，正确。

注意：两数之和题目保证“恰好有一个答案”，所以代码里没有答案时的return new int[0]永远不会走到，但写上会更安全。有些刷题网站在没有答案时会期望你返回空数组或null，写代码前先看清楚题目约定。

复杂度分析：一次遍历，每次只做一次containsKey和一次put，时间O(n)。map最多存储n个键值对，空间O(n)。这就是典型的用空间换时间，相比暴力的O(n^2)，在n较大时提升非常明显。

5.3 面试官可能会怎么追问

两数之和是面试高频题，因为太经典，面试官通常会往上加条件：

• 如果数组是有序的，可不可以用双指针？可以。左指针指向开头，右指针指向末尾，和大于target就右移右指针，和小于target就左移左指针，时间O(n)，空间O(1)。不过题目要求返回下标时，需要先记住原始下标，或者数据本身有序但要求返回数值，这时双指针就很香。
• 如果要求输出所有不重复的数字对，而不是下标？那需要用排序加双指针，或者用Set配合去重，HashMap就不太合适了。
• 三数之和、四数之和怎么处理？这些题目虽然从两数之和延伸出来，但解法逻辑完全不同，哈希表去重比较麻烦，排序加双指针加去重是主流做法。

我在一刷两数之和时，只觉得这题“好简单，背下来就行”。二刷才真正理解：为什么用哈希表、为什么先查再放、复杂度怎么分析、和后续题目的关系是什么。这种“从背答案到理解答案”的过程，才是二刷最有价值的地方。

6. 训练营第六天复盘：一刷和二刷最大的区别

6.1 一刷时我最容易犯的四个错

先说我自己一刷时踩过的坑，如果你也遇到过，别慌，太正常了。

第一，拿到题就无脑上HashMap。242题明明数组就够，我非得写个Map<Character, Integer>，代码又长又难读。二刷后才明白，先看数据范围，再决定用什么结构，是哈希专题的第一步。

第二，349题忘了去重。用Set存了nums1，遍历nums2时一发现存在就直接加到结果数组，结果输出了一堆重复值。后来才想到要用第二个Set，或者像数组标记法那样收集后立刻置false。

第三，202题没有主动想到用Set判循环。我当时的想法是“这题是不是要用数学推导证明什么”，完全跑偏了。实际上就是用哈希记住出现过的数，遇到重复就说明死循环。

第四，1题搞反了先放再查的顺序。这个坑我上面已经详细解释过，[3,3]这个测试用例能精准命中。一刷时我甚至没意识到这个顺序问题，只是AC了就没想太多，直到二刷手动推用例才发现。

6.2 二刷后我总结的哈希表做题模板

二刷之后，我给自己整理了一套做题顺序，分享给你：

1. 先读题，确认数据范围。数字范围小且连续，优先想数组；范围大或类型是字符串、对象，再想Set或Map。
2. 再想清楚需要什么信息。只需要判断存在，用Set；需要保存下标或次数，用Map；需要用下标当键，用数组。
3. 最后才写代码。写完手动跑一个简单测试用例，尤其检查会不会重复使用同一元素、会不会重复收集结果、有没有环路风险。

今天四道题可以用一张表串起来：

6.3 关于Java哈希表输出的几个小经验

因为我是用Java刷题的，这里单独说几个Java哈希表输出相关的经验，也是二刷时注意到的。

第一，HashMap和HashSet的遍历顺序不稳定。今天349题用Set收集结果后直接转数组，每次提交返回的顺序可能都不一样。题目不要求顺序，所以没事，但如果你在本地调试时发现输出顺序跟自己想的不一样，不要怀疑算法错了，先看题目是否要求顺序。

第二，HashMap的键如果是Integer，注意自动装箱。比如map.containsKey(complement)时，complement是int，会自动装箱成Integer，Java的Integer缓存只在-128到127之间生效，超过这个范围就是不同对象了，但HashMap内部用的equals比较，所以不用担心，Integer的equals比较的是值。

第三，如果想让输出有序，可以考虑TreeSet或者TreeMap。不过大多数算法题不要求有序，用TreeSet反而多一个O(log n)的插入成本，没必要。

6.4 关于复习节奏的一点建议

训练营的节奏很快，第六天已经进入第二个专题。我的体会是：每天的新题要认真做，但隔两三天一定要回头把前面的题重新手写一遍。比如今天这四道题，一周后再写一次，别看好几篇题解，直接凭记忆和思路写。能一次性通过，才是真正掌握了。

我在二刷时给自己定的标准是：每道题不仅能写出代码，还要能说清楚“为什么这么做”。比如242为什么用数组而不用Map，349为什么要第二个Set去重，202为什么一定会进入循环，1为什么必须先进Map查再放。这些“为什么”才是面试时真正会被问到的。

今天这四道题全部过完，哈希表这个专题算是在我心里真正立住了。我个人最大的体会是：哈希表不难，难的是想清楚“我把什么当key、把什么当value、用什么结构当容器”。这是需要靠做题量喂出来的感觉，不是看一两篇题解就能会的。

最后再分享一个小技巧：刷题时遇到重复出现、快速查找、状态循环这类字眼，先别急着写代码，停下来问自己一句“值域有多大？”。如果值域小到能用数组，就别让HashMap折腾你自己了。希望这篇二刷笔记能帮你在哈希表这个专题上少走点弯路，明天继续。Good luck and enjoy!