企业官网建设流程全解析

哈希表，Day6，part01——如果你也在一轮轮啃算法训练营的进度，这四个字应该不陌生。终于，我们从数组、链表、双指针这些线性结构走进了“以空间换时间”的经典领域。哈希表是算法面试里性价比极高的一块：概念不复杂，代码模板固定，刷题见效快。这套课的定位是哈希表入门第一讲，核心就两件事：什么时候用哈希结构，以及数组、HashSet、HashMap之间怎么选。把这四道经典题吃透——有效的字母异位词、两个数组的交集、快乐数、两数之和——后续再遇到哈希相关题目，基本就是套模板。

这份笔记是我自己带训练营复盘时整理的完整版。除了每道题的思路和代码，还写了不少我在实际刷题和带学员时反复踩过的坑。如果你正在准备校招、跳槽或者单纯想把算法基础打牢，这一篇值得认真看完。

1. 哈希表基础：先想清楚它到底解决了什么问题

1.1 为什么要用哈希表：从“翻箱倒柜”说起

数组要查找一个元素，通常只能从头扫到尾，平均时间复杂度O(n)。链表更慢，要找一个值必须沿着指针一个个next。倒不是说数组和链表一无是处，它们的优势在插入顺序、内存连续、动态长度这些方面。可一旦场景变成“频繁判断某个值是否存在”“统计某个值出现了几次”“查找某个键对应的信息”，线性扫描就是浪费。

哈希表解决的核心问题，就是把“查找”从“逐个比”变成“直接去”。打个比方：快递驿站如果没有货架编号，你要找一件包裹，只能翻遍所有箱子；如果有编号区间，快递员告诉你“B区07号”，你直接走到对应位置就行。哈希表干的事，就是给每个元素算出一个“编号”，存储时按编号放，查找时按编号取，平均复杂度几乎O(1)。

很多训练营前几天的内容，比如链表反转、双指针，是在训练你怎么“走完一条路”。哈希表则是训练你“别走，直接跳过去”。这种思路转变，是Day6真正要练的东西。

1.2 哈希函数是怎么把数据映射到位置的

哈希函数本质上是一段映射规则：输入任意数据，输出一个固定范围内的数字。在编程语言内置的HashMap或HashSet里，这个映射规则已经封装好了，你不需要自己写。但底层仍然在做三件事：计算哈希码、压缩到桶范围、在桶内查找。

有两个基础概念必须知道：一是哈希冲突。两个不同的key算出了同一个下标，就会撞车，语言内部会处理，Java里HashMap用的是链地址法加红黑树优化，Python的dict也做了类似处理。二是因为存在冲突，所以哈希表的查找是“平均O(1)”，不是“严格O(1)”。极端场景下大量冲突，退化成链表遍历，复杂度最差O(n)。对刷题来说，99%的情况都不用担心这个，但面试官问“哈希表时间复杂度为什么是O(1)”时，你要能接住这两个概念。

1.3 数组、HashSet、HashMap怎么选：一张表理顺

很多新手看到“哈希表”三个字就只想到HashMap，其实哈希思想包含三种常用结构。选错了结构，代码也能写出来，但可能多开一倍的变量，或者多绕几步逻辑。我在训练营里反复强调选择逻辑，可以浓缩成一张表：

训练营part01的四道题刚好把这三种结构各用了一遍：字母异位词用数组，数组交集用HashSet，快乐数和两数之和用HashMap。一次课下来，三种结构的适用场景基本就清楚了。

1.4 哈希表不是银弹：理解它的边界

哈希表也不是万能药。如果题目要求保持输入序列顺序、要求输出所有排列组合、要求在连续内存上做某种运算，哈希表未必合适。它最大的代价是空间，所谓“空间换时间”，就是用额外存储换取查找速度。所以刷题时要先问自己：我想加速的是哪个操作？这个操作是查找、去重、统计还是映射？想清楚需求，再选结构。训练营前四天学的双指针、滑动窗口，很多场景依然有不可替代的价值，不是说学了哈希就把前面全丢掉。

2. 第一题：有效的字母异位词——数组当哈希表的入门课

2.1 题目拆解：什么叫字母异位词

题目内容很直白：给定两个字符串s和t，判断它们是不是字母异位词。字母异位词的意思是，两个字符串包含的字母种类相同，每种字母的数量也相同，只是排列顺序可能完全不同。经典例子就是“anagram”和“nagaram”，字母一样，顺序打乱。

拆解成三个判断点：第一，两个字符串长度必须相同，否则字母数量不可能对得上；第二，字符种类必须完全一致；第三，每种字符出现的次数必须完全一致。这三个点缺一不可。很多同学第一次做这道题时，只想到“统计字母个数，然后比较两张表”，这个方向是对的，但没人告诉他可以只用“一张表”通过加减法搞定，这正是这道题的精髓。

2.2 先想到的笨办法：排序后比较

最容易想到的解法是：把s和t分别转成字符数组，排序，再比较两个数组是否相等。字符串长度n时，排序复杂度O(n log n)，空间取决于语言实现。这个解法能过测试，思路也完全正确。但面试官大概率会追问一句：“能不能优化到O(n)？”这就是哈希表的入场点。

排序解法还有一个隐藏问题：它把“判断两个字符串是否包含相同字符集合”变成了“判断排序后的序列是否相同”，逻辑没问题，但一旦题目条件改成“不区分大小写”“只统计字母不统计数字”等变体，排序解法会立刻变质。哈希表解法却很容易扩展。

2.3 哈希思路：用一张“打卡表”同时处理两个字符串

核心思路是维护一个长度为26的数组，下标0~25对应a到z。遍历s时，每遇到一个字符就在对应下标上+1，表示“s里这种字母多了一个”；遍历t时，在对应下标上-1，表示“t里这种字母多了一个”。如果最终数组里所有值都是0，说明s多出来的每一个字母，都被t里相同的字母抵消掉了，字符种类和数量完全一致。

用生活类比解释：假设两个人都往同一个筐里放水果，A每放一个苹果记+1，B每放一个苹果记-1。最后筐为空，说明B拿走的苹果种类和数量和A放进来的完全一样。这就是字母异位词的直观版本。

public boolean isAnagram(String s, String t) { if (s.length() != t.length()) { return false; } int[] table = new int[26]; for (int i = 0; i < s.length(); i++) { table[s.charAt(i) - 'a']++; table[t.charAt(i) - 'a']--; } for (int count : table) { if (count != 0) { return false; } } return true; }

代码里最关键的两个细节：一是s.charAt(i) - 'a'，字符相减得到的就是0到25的下标，这是字符转数字的常用技巧；二是两个遍历放在同一个循环里，因为已经限定了长度相同，可以同时处理两条字符串，比先遍历s再遍历t更简洁。

2.4 为什么使用数组而不是HashMap

很多同学第一反应是用Map<Character, Integer>统计频次。这样当然能过，但性能上没优势，代码也长一些。原因在于题目明确限制了“只有小写字母”，范围固定在26个。数组的天然优势是，下标本身就是哈希值，直接通过字符计算下标，一步到位，没有HashMap的哈希计算、装箱拆箱、equals比较的开销。

刷题过程中，希望大家养成一个条件反射：数据范围是什么？如果范围是已知且可数的，优先考虑数组当哈希表。这道题的范围是26个字母，数组长度26就够；后面遇到“元素值在0到1000之间”的题目，数组长度1001也是一个道理。数组当哈希表其实是用“下标”代替“哈希函数”，最朴素也最稳定。

2.5 复杂度分析与扩展思路

时间上，一次遍历O(n)，一次数组检查O(1)，总复杂度O(n)。空间上，固定数组长度26，O(1)。与排序法的O(n log n)相比，提升了一个量级。这道题的扩展版本也很常见：如果输入不仅仅是小写字母，而是任意Unicode字符，数组长度就无法确定了，这时候要改用Map<Character, Integer>，思路完全一样，只是把“数组”换成“字典”。能讲出这两种实现的切换理由，面试官会觉得你是真的理解问题，而不是背模板。

3. 第二题：两个数组的交集——HashSet去重与集合语义

3.1 题目拆解：理解“唯一”和“顺序不限”很重要

题目如下：给两个整数数组nums1和nums2，返回它们的交集。输出结果中的每个元素必须唯一，顺序不限。两点需要注意：“唯一”意味着结果要做去重，就算原数组里3出现了十次，交集中3也只能出现一次；“顺序不限”意味着我们不需要维护元素的相对位置，这让Set解法成为天然选择。

这题不像字母异位词有严格的字符范围限制，数组元素可能是任意整数，所以不能用固定长度的数组当哈希表，要用HashSet。HashSet的核心语义就是“集合”：元素无重复、判断contains非常高效。用它来做交集，一条主路走到底。

3.2 不用HashSet的翻车现场

有一个新手解法很容易想到：把两个数组都排序，然后用双指针同时扫描，遇到相同元素就加入结果。思路有道理，但实际写起来很痛苦。双指针遇到连续重复元素时，必须跳过重复值，否则结果里会出现重复数字。为了跳过重复，又需要额外的while循环，边界条件稍不注意就数组越界。

我上一期训练营就有个A同学，用双指针写了半小时，代码三四十行，最后测试还差几个用例没过。换成HashSet之后，十行代码解决问题。这不是说双指针不好，而是这个场景下它不够“匹配”。题目已经告诉你结果元素唯一，那选一个天生去重的结构才是最省力的。

3.3 HashSet标准解法：两个Set各司其职

标准解法分三步：第一步，遍历nums1，把所有元素放入HashSet set1，顺便完成去重；第二步，遍历nums2，如果set1中有当前元素，说明它是交集的一部分，把它加入resultSet，这里的resultSet也是HashSet，用来避免交集本身重复；第三步，把resultSet转成int[]数组返回。

public int[] intersection(int[] nums1, int[] nums2) { 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[] result = new int[resultSet.size()]; int index = 0; for (int num : resultSet) { result[index++] = num; } return result; }

这里需要解释一个初学者容易懵的点：为什么需要两个Set？第一个Set用来去重原数组中的元素，让“是否出现过”的判断不受重复影响；第二个Set用来去重交集结果。如果把两个职责混在一起，比如只用一个set1，遍历nums2时发现元素在set1里就直接加入结果数组，那如果nums2本身有重复元素，结果数组就会重复。这就是“唯一”两个字逼出来的细节。

3.4 隐藏进阶：如果数字范围很小呢

这道题其实有一个很常见的变体：如果题目改成“数组中的元素值在0到1000之间”，那就可以放弃HashSet，改用布尔数组当哈希表。长度为1001的boolean数组，遍历nums1时把下标位置标记为true，遍历nums2时检查对应下标是否已经标记。这个思路和字母异位词完全一脉相承。

为什么数组方案更好？因为它是纯下标的随机访问，没有哈希运算、没有碰撞问题、也没有Integer装箱的开销。在数据量极大但值域很小的场景下，数组方案的时间和空间表现都比HashSet更稳定。训练营里做这道题，目的之一就是让你记住：看到“值域有限”四个字，第一反应应该是数组，而不是Map或Set。

3.5 复杂度与后续题目的隐藏联系

时间复杂度O(m+n)，两个数组各遍历一次。空间上最坏情况是较小的那个数组的所有元素都存入Set，O(min(m, n))。这道题做完，后续你还会遇到“两个数组的交集II”，那道题要求结果统计重复次数，需要用HashMap记录频次而不是HashSet。区别就在“要不要统计个数”上，一遍下来，集合和映射的边界会非常清楚。

4. 第三题：快乐数——哈希表检测“死循环”

4.1 题目拆解：什么时候停下是关键

快乐数的定义大家应该都看过：对一个正整数，每一次将该数的每位数字平方后求和，得到一个新数。反复执行这个过程，如果最终能变成1，那这个数就是快乐数；如果陷入一个不包含1的循环，永远无法变成1，那它不是快乐数。举一个例子，19是快乐数：1²+9²=82，8²+2²=68，6²+8²=100，1²+0²+0²=1，成功收敛到1。而2不是快乐数：2²=4，4²=16，1²+6²=37，3²+7²=58，5²+8²=89，8²+9²=145，1²+4²+5²=42，4²+2²=20，2²+0²=4，注意看，4又出现了，进入循环。

这道题初看很简单，就是一个while循环不断算平方和。难的是：循环什么时候终止？如果只用while(n != 1)，那遇到非快乐数会永远算下去，直接死循环。真正要解决的核心问题就是“怎么判断这个数已经出现过”。而“判断某个值是否出现过”，正是哈希表最舒适的应用场景。

4.2 用HashSet记录历史状态，检测循环

思路是这样的：用一个HashSet保存所有出现过的数。在while循环里反复操作：如果当前数等于1，直接返回true；如果当前数已经出现过了，说明进入了循环，返回false；否则把当前数加入HashSet，然后计算下一轮的平方和。

为什么判断“已经出现过”就能证明不是快乐数？因为这个变换过程是确定性的，同一个数每次算出的下一个数完全相同。一旦一个数重复出现，后续的序列会和上一轮一模一样，永远不可能跳出这个环，也永远到不了1。

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

getNext这个函数要单独抽出来，因为主循环里需要反复调用。计算平方和的常见写法是对n不断取余和整除，先把个位数取出来，再加到sum里，然后去掉个位，直到n变成0。这个写法很基础，但一定要熟练，快乐数的后续变体题里还会用到。

4.3 为什么不能直接循环100次或1000次

有人会想到一个“偷懒”办法：让循环最多跑100次，超过就说明不是快乐数。测试用例可能能过，但这个解法是脆弱的，因为循环的长度不是固定的，不同数字进入循环的步数完全不同，而且题目没有保证数字范围。100次上限没有理论依据，万一测试数据需要101步才走到1，你的解法就错了。使用HashSet才是最通用、最符合题目本质的判断方式。

这道题的价值在于，它教会你一个重要的思维模型：当问题描述中反复出现“不断变换”“最终会变成”“一旦重复就永远重复”这类字眼时，本质上是在考“环检测”。哈希表可以记录访问历史，快慢指针可以在O(1)空间下检测环。面试中我会建议先写HashSet版本，因为它逻辑最直观，如果面试官追问“能不能优化空间”，再引出快慢指针思路。

4.4 一个让人安心的细节：计算过程中数字不会无限变大

有人可能会担心，这个平方和过程会不会越算越大，导致int溢出？有一个已知的事实是，快乐数计算过程中，数值会收敛到某个范围内，不会无限膨胀。简单估算一下：一个十位数，每位最大是9，平方和最多约810，远小于原数；一个一位数变成平方和后最多81。事实上在进入判断循环时，数字很快会掉到几百以内。所以int完全够用，不用使用long。

5. 第四题：两数之和——HashMap存储“历史下标”

5.1 题目拆解：几乎每场算法面试都会见面的老朋友

两数之和这道题：给定一个整数数组nums和一个目标值target，请在数组中找出和等于目标值的两个整数，返回它们的下标。题目保证只有一组答案，且同一个元素不能使用两次。这道题的经典程度不必多说，几乎所有训练营都会把它放到哈希表part01，它也是最适合讲清楚“为什么需要HashMap”的题目。

表面能看出两个信息：要返回下标，所以不能只判断存在，还要能取出位置；数组元素可能有负数、有重复值，各种边界情况都要cover。很多人第一次看完题解觉得不难，但真正自己写的时候，最容易在“先存map还是先查map”这个细节上栽跟头。

5.2 暴力解法的问题在哪里

最直观的解法是双重循环：外层固定一个数，内层遍历它后面的所有数，判断两个数的和是否等于target。时间复杂度O(n²)，空间O(1)。如果数组长度是10⁴，最坏情况下要执行约5000万次比较，跑起来明显吃力。更关键的问题是，每次内层循环都在重复“查找target - nums[i]等于什么”这件事，完全没利用外层已经遍历过的信息。

哈希表优化的本质，就是把内层循环的“查找”，从O(n)的线性扫描，变成O(1)的哈希查找。你不需要再从数组开头找，只需要看一眼这个“补数”之前有没有出现过。

5.3 标准解法：边查边放，用HashMap记录“来时的路”

核心思路一句话：遍历数组时，先把之前处理过的数字和下标放进HashMap，然后在每一轮查找当前数字的“补数”是否已经在map里。如果在，就找到了答案；如果不在，就把当前数字和下标放进去，继续往后走。

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

代码看起来很短，但每一步都有讲究。为什么要“边查边放”？因为这样可以保证map里的元素全部是当前下标之前的“历史元素”，查找补数时不会把当前元素自己当作答案。比如nums=[3, 2, 4], target=6，遍历到i=0时，need=3，map为空，于是put(3, 0)；到i=2时，need=2，map中有2吗？没有，于是put(2, 1)不是，其实遍历到i=1时nums[1]=2，need=4，map没有4，put(2,1)；到i=2时nums[2]=4，need=2，map里面有key=2且下标是1，返回[1,2]。这个计算过程完美避开了同一元素复用的坑。

5.4 最常见错误：先把所有数据放进去再查找

新手很容易写成两步走：第一次遍历把全部nums[i]和下标i放入map，第二次遍历再查找target - nums[i]。这样做的最大风险是，当target恰好是某个数的两倍时，会把同一个元素用两次。

例如nums=[3, 2, 4], target=6，如果先全部放入map，key为3的下标是0。第二次遍历到i=0时，need=3，map.get(3)返回0，答案变成[0,0]，这明显不对，用了同一个元素两次。更糟糕的是，如果数组里有两个3，后放的会覆盖先放的，答案的下标又变得不可预测。所以标准解法坚持“边查边放”，map里永远只保存已经处理过的元素，这就是避免复用的安全锁。

5.5 一个容易忽略的边界：重复值会覆盖下标吗

如果数组是[3, 3, 4]，target=6，会不会有问题？走一遍过程：i=0时need=3，map为空，put(3, 0)；i=1时need=3，map里key=3的下标是0，找到了，返回[0,1]。这里没有触发覆盖问题，因为在把第二个3放入map之前，已经先查完了，查到了就直接返回。所以重复值是安全处理的。

但如果题目要求返回所有满足条件的结果对，而不是“只有一组答案”，那就需要换一种策略，先按值分组记录所有下标，再做配对，还要注意不能重复使用同一个下标的组合。那是另一道扩展题，part01阶段只需要掌握标准解法即可。

5.6 为什么是HashMap而不是HashSet

因为题目要返回下标，HashSet只能判断某个数字是否存在，取不出它的索引。HashMap的key存数字，value存下标，把“存在性判断”和“位置访问”两件事一次搞定。这个区分非常重要：以后做题，只要发现“判断完还要拿到关联信息”，第一反应就应该是HashMap。训练营里有同学问，能不能用数组排序加二分法做两数之和，当然能，但排序会打乱原数组的下标，必须额外记录原始位置，复杂度也不占优。哈希表几乎是这道题的最优解。

6. 常见问题与实战心得

6.1 数组、Set、Map速查表

训练营到这期，大家已经开始接触好几道不同结构的题目了，我整理了一张速查表，后面做题时可以直接对着选：

记住一个原则：能用数组就别开Map，能用HashSet就别开HashMap。结构和需求越匹配，代码越短，越不容易出错。

6.2 五个容易踩的坑

第一个坑，字母异位词只遍历s做统计，忘了遍历t做抵消，最后拿两张表比较也能做，但容易在长度判断上遗漏。建议直接用加减法，一步到位。

第二个坑，数组交集只用一个Set，结果数组出现重复元素。这是因为忘记了nums2本身可能有重复，正确做法是再用一个Set存结果。

第三个坑，快乐数while循环没有终止条件，一直算到超时。记住“重复出现就是退出信号”。

第四个坑，两数之和先全存后查找，同一元素被使用两次。解决方法是边查边放，别偷懒。

第五个坑，混淆HashMap和HashSet的用途。比如返回下标用HashSet，结果取不到位置，或者统计次数用了Set导致丢失频次。这个坑听起来低级，但我在带训练营时几乎每期都能见到。

6.3 一个值得背下来的模板

哈希表part01学完之后，其实可以提炼出一个万能模板。判断是否存在用Set，需要存储关联数据用Map，数据范围固定优先开数组。模板不是死代码，而是“看到题目后自动化产生选型”的思维路径。做题时先问自己：需要存什么？需要查什么？返回什么？三个问题回答完，结构就定了。

6.4 训练营式复盘流程：每天20分钟巩固

我个人的习惯是每天晚上用20分钟做复盘，训练营所有题都可以套这个流程：第一步，不看代码，把题目翻译成数据结构需求；第二步，写出暴力解并分析复杂度；第三步，想清楚哈希优化的点在哪里；第四步，对照自己的代码和标准模板找差异。四道题花费20分钟是够的，但收获往往比闷头刷十道新题更大。算法训练营的速度很快，不复盘容易忘，特别是哈希表的“选型思维”，很多同学隔两天就又退回到“拿到题就遍历”的老路上了。

最后再分享一个我自己带训练营的心得：哈希表part01这四道题，价值不在题本身，而在于建立一种条件反射。看到“查找”“去重”“统计次数”“记录状态”这些关键词，脑子里立刻蹦出哈希结构。这种感觉不是看出来的，是写出来的。我上一期带学员复盘时，有个同学A跟我说，前五天总觉得题目之间是孤立的，Day6把四个题刷完，突然发现所有题都在做同一件事：把遍历过的信息存下来，供后面的查询使用。这个顿悟，比任何模板都值钱。后续再学哈希表的进阶用法，比如分组统计、滑动窗口配合HashMap、设计LRU缓存，其实都是在这个基础上做加法。