企业官网建设流程全解析

刷题打卡到第 6 天，正式进入哈希表 part1。这个节点很有意思：前面刚啃完数组和链表，你以为自己对遍历、指针、时间复杂度已经够熟了，结果碰到“在一个数组里找两个数，让它们的和等于目标值”这种题，还是会被暴力解带偏。哈希表这一部分，练的不是背 API，而是建立一种空间换时间的直觉。这篇就当作一份 Day 6 的完整笔记，覆盖哈希表底层原理、四道经典题目的思路拆解、完整可 AC 的代码，以及我实际刷题过程中踩过的几个坑。正在刷题的新手可以照着过一遍；已经有基础的人可以直接跳到第 4 章看避坑清单。

1. 为什么数组、链表之后，Day 6 要单独练哈希表

1.1 查找的痛点与哈希表的解题思路

数组和链表学完之后，我们最容易形成的一个惯性是：要找某个元素，那就遍历呗。数组的线性查找是 O(n)，如果数组有序，可以用二分查找降到 O(log n)。看起来已经很不错了，但刷题中经常出现更苛刻的需求：比如“同一个集合里我要反复查找某个值是否存在”，一次查找 O(n)，查 m 次就是 O(n*m)。一旦数据规模上去，超时几乎是必然的。

这时候就该哈希表出场了。哈希表的核心思路是：不通过遍历去找，而是通过一个哈希函数，把“要查找的键”直接换算成“存储位置”，然后一步到位拿到数据。生活中的例子就是查字典：你不会从第一页开始翻，而是按拼音或部首直接定位到某个区间。哈希表做的就是这个事，平均时间复杂度是 O(1)，代价是多占用一些内存。所以理解哈希表，第一步不是背代码，而是接受“用空间换时间”这个思想。

1.2 哈希函数与哈希碰撞

哈希表底层要解决两件事：怎么把键映射到位置，以及多个键映射到同一个位置时怎么办。第一件事靠哈希函数，常见的做法是取模。假设底层数组长度是 capacity，一个整数键 key 的哈希值就是 key % capacity。字符串键则先经过某种哈希算法算出整数，再取模。

第二件事就是哈希碰撞。两个不同的键，经过哈希函数后落到了同一个下标，这就叫碰撞。解决碰撞有两大类主流方案：链地址法和开放定址法。链地址法是在每个数组下标挂一个链表，碰撞了就挂到同一个链表上，C++ 的 unordered_map 底层基本是这种思路；开放定址法是从当前位置继续往后找空位，Python 的 dict 底层用的是类似思路。刷题时很少需要自己实现哈希表，但理解碰撞能帮你解释一个现象：为什么哈希表的最坏时间复杂度是 O(n)，而不是 O(1)。当大量键碰撞到同一条链上，查找就会退化成线性查找。不过在正常刷题和工程实践中，哈希函数设计合理，平均性能还是 O(1)。

1.3 从使用场景反推实现方式：数组、Set、Map

哈希表的具体实现不只有一种。按使用场景，Day 6 至少要分清三种：数组、集合 Set、映射 Map。很多人第一天会纠结“题目说用哈希表，我到底用数组还是用 Map？”，答案其实就在数据范围里。

如果键的取值范围很小且连续，比如 26 个小写字母，直接用数组最合适。数组本身就是一张天然的哈希表，索引是键，值是统计信息，不需要额外计算哈希函数，访问速度比通用哈希表还快。如果只需要判断“元素是否出现过”，不关心次数，也不关心对应关系，那就用 Set。Set 会自动去重，尤其适合交集、查重这类题目。如果不仅需要判断存在，还要保存一个关联值，比如“这个数字在数组中的下标”，那就必须用 Map。三种结构的适用场景，我整理了一个表格：

这个表格在 Day 6 后半段会反复用到。先把它刻在脑子里，再往下看题。

2. Day 6 四道经典题：表面不同，内里全是哈希

2.1 字母异位词判定：用数组模拟哈希表

第一道题是判断两个字符串是不是字母异位词。字母异位词的意思是，两个字符串长度相同，字符种类和数量完全相同，只是排列顺序不同。比如 “aabc” 和 “abca” 就是异位词。

最容易想到的办法是先排序再比较。排序的时间复杂度是 O(n log n)，也能 AC，但哈希表解法能把复杂度降到 O(n)。因为题目明确说字符串只包含小写字母，这个限制就决定了用数组最合适：开一个长度为 26 的计数数组，遍历第一个字符串时，每个字符对应的格子加 1；遍历第二个字符串时，每个字符对应的格子减 1。如果最后数组里所有位置都是 0，说明两个字符串的字符数量完全一致。

这里要特别理解一个操作：字符减字符。比如ord(s[i]) - ord('a')，得到的是 0 到 25 之间的整数，正好作为数组下标。这是用数组模拟哈希表时的标准操作，你最好能条件反射地写出来，而不是每次都去百度。

2.2 数组交集：Set 去重与交集运算

第二道题是求两个数组的交集。题目要求输出结果中的每个元素唯一，不考虑顺序。如果不用哈希表，最简单的办法是两层循环逐个比较，时间复杂度 O(n*m)，而且还要额外处理去重，非常难受。

换成 Set 之后思路瞬间清楚：先把第一个数组转成 Set，去掉重复元素，再遍历第二个数组，判断每个元素是否在第一个 Set 中出现过。出现过就加入结果集合，最后再把结果集合转成数组返回。这里一个小细节是：结果也要去重，所以用 Set 收集结果比用列表更稳。如果你不想显式收集结果，也可以直接取两个 Set 的交集：set1 & set2，时间复杂度同样是 O(n + m)。核心思想是判断“存不存在”，这正是 Set 的主场。

这道题的难点不在代码，而在你能不能意识到：看到“去重”“是否存在”“交集”这些词，要第一时间想到哈希表。这比能默写某个库函数重要得多。

2.3 快乐数：哈希表不止用来去重，还能检测循环

第三道题是快乐数。一个正整数，每次把各位数字平方后求和，得到一个新数，然后重复这个过程。如果最终能变成 1，就是快乐数；如果陷入一个不包含 1 的循环，就不是快乐数。

很多新手看到这个题第一反应是硬算，算到什么时候算不出来就懵了。关键点在于：如果不快乐，这个过程会无限循环，程序不能真的无限跑下去。怎么知道循环了？把每次出现过的数字都记下来，如果某个数字第二次出现，说明开始重复了，也就永远到不了 1。这个“记录历史出现”的需求，用 Set 再合适不过。

这里还要注意一个数学事实：每次计算平方和后，数字会迅速变小。比如 999 的平方和是 243，三位数变两位数。所以用 Set 记录不会导致内存爆炸。有人会问能不能用快慢指针检测循环，当然可以，但哈希表解法更直观，也更贴合 Day 6 的主题。先掌握哈希表方案，再想优化方案也不迟。

2.4 两数之和：第一次接触“补数查表”

第四道题是整个 part1 的压轴题：给定一个整数数组和一个目标值，找出和为 target 的两个数的下标。暴力解法是两层循环枚举所有组合，时间复杂度 O(n²)，这在数据量大时基本不可取。

哈希表解法引入了一个很重要的概念：补数。当遍历到当前数字 num 时，我要找的另一个数字是 target - num。把遍历过的数字存进 Map，键是数字本身，值是它对应的下标。每次先查“补数是否已经在 Map 里”，如果在，直接返回补数的下标和当前下标；如果不在，把当前数字和下标存进去。这样一次遍历就能完成，时间复杂度 O(n)。

这道题是后面很多“N 数之和”题目的地基。你需要牢牢记住“遍历时边查边存”这个顺序，不要先把整个数组存进 Map 再遍历，否则遇到重复元素会很麻烦。关于这个坑，第 4 章我会专门展开。

3. 完整实操：从读题到 AC 的关键代码

3.1 练习环境与通用模板

刷题环境不需要花哨，在线判题系统选一个自己顺手的就行。Day 6 的四道题，我用 Python 来写，因为代码量小、逻辑直观，适合把注意力放在算法思想上。但不管用什么语言，核心思路都一样。

Python 里对应三种哈希结构的分别是：列表、set、dict。列表做数组型哈希，set 对应 Set，dict 对应 Map。写题之前先问自己一句：这道题需要统计数量吗？需要记录下标吗？还是只需要判重？然后选结构。这个思考过程比代码本身更值钱。

另外，我习惯把平方和计算这种小逻辑单独抽成一个函数，比如快乐数里的sum(int(x) ** 2 for x in str(n))。单独写可以让主函数更清晰，调试时也方便 print 输出中间值。刚开始刷题不用追求代码最短，先追求一眼能看懂。

3.2 四道题完整实现与复杂度分析

第一道，字母异位词判定：

def is_anagram(s: str, t: str) -> bool: if len(s) != len(t): return False count = [0] * 26 for ch in s: count[ord(ch) - ord('a')] += 1 for ch in t: count[ord(ch) - ord('a')] -= 1 for c in count: if c != 0: return False return True

第二道，数组交集：

def intersection(nums1: list, nums2: list) -> list: set1 = set(nums1) res = set() for x in nums2: if x in set1: res.add(x) return list(res)

第三道，快乐数：

def get_sum_of_squares(n: int) -> int: return sum(int(x) ** 2 for x in str(n)) def is_happy(n: int) -> bool: seen = set() while n != 1 and n not in seen: seen.add(n) n = get_sum_of_squares(n) return n == 1

第四道，两数之和：

def two_sum(nums: list, target: int) -> list: seen = {} for i, num in enumerate(nums): complement = target - num if complement in seen: return [seen[complement], i] seen[num] = i return []

我实测下来，这四段代码都是简洁且不容易出错的版本。时间复杂度和空间复杂度对比如下：

3.3 实测体会：哪些代码看似能跑但会翻车

字母异位词那题，注意先判断长度。如果长度不同，直接返回 False，这样后面的计数代码就不用处理“一个字符串多出一个字符”的复杂情况。我一开始没有判断长度，而是直接在遍历第二个字符串时判断下标会不会小于 0，也可以判，但代码会绕很多。

数组交集那题，最容易翻车的写法是两层循环加if x not in res。这样虽然也能 AC，但时间复杂度高。不要以为交了就算成功，刷题的意义在于逼自己想出更优解。用 Set 之后，去重和查重都顺手解决，代码也更接近工程中的写法。

快乐数的细节是seen集合要记录中间值，而不是记录原始 n。有一个常见的错误写法：一开始就把原始 n 放进集合，循环条件里又判断 n 是否在集合，导致第一次就退出循环。你应该在每次更新 n 之前，把当前 n 放进集合；或者用一个先保存后更新的代码顺序。上面给出的是先判断后更新，逻辑清晰，推荐照这个写。

两数之和的返回顺序也有讲究。return [seen[complement], i]返回的是补数下标在前，当前下标在后。题目如果没有特殊要求，这个顺序就可以；如果要求相对顺序，你需要先存更早的下标，再返回时就天然满足。

4. Day 6 最容易踩的坑：数组、Set、Map 选择与边界

4.1 “什么时候用哪种哈希结构”的判断标准

刷完四道题，你会发现它们分别对应了数组、Set、Map 三种结构。很多新人会困惑：两数之和里，能不能用 Set 而不是 Map？不能，因为不仅要判断补数存在，还要拿到补数的下标。数组交集里，能不能用数组？能，但必须知道输入数据的范围，如果数字范围很大且稀疏，开一个几百万长度的数组就会很浪费。字母异位词里，能不能用 Map？能，但比数组多了一次哈希计算，在小写字母这种固定小范围场景下属于性能浪费。

我把选择判断写成一个三步流程，直接按顺序执行：

1. 先看键的范围是否已知且连续。比如 26 个小写字母、0 到 100 分、字符集固定，用数组。
2. 再看是否需要保存“键之外的信息”。不需要保存，用 Set；需要保存次数、下标、对象等，用 Map。
3. 最后看内存是否敏感。如果键的范围很大，但极少数键会被用到，用数组就是浪费，此时 Set/Map 更合理。

这三步每次都花十秒钟想一下，比写完了再回头重构要高效得多。

4.2 边界条件与常见错误速查

刷题的时候边界条件往往比主逻辑更能决定成败。Day 6 这几道题，我整理了一个速查表，你可以直接收藏：

空数组和空字符串看起来简单，但很多人会在意这些无效数据上。最好的习惯是写上详细注释，在代码开头处理掉最明显的特殊情况。比如字母异位词，长度不等直接 false；数组交集，如果nums1或nums2为空，直接返回空列表。这不会让你的算法变慢，只会让阅读代码的人更舒服。

4.3 我踩过的三个具体失败案例

案例一：两数之和先存全表。我第一次写两数之和，想着先把所有数字的下标存进 dict，再遍历一遍找补数。遇到nums=[3,3], target=6时，dict 里下标会被覆盖成 1，结果遍历时查到补数还是自己，但下标已经错了。后来改成了“边查边存”，问题立刻消失。记住这个顺序很重要。

案例二：快乐数循环条件写反。我一开始写成while n not in seen and n != 1，然后进入循环后先计算平方和，再把 old 值加入 seen。这导致了没把最初的 n 加入集合，在 n=2 时卡进了死循环。后来调整成“先判断是否见过，再把当前 n 加入集合，最后更新 n”的顺序才稳定。这个逻辑陷阱，写代码时很容易忽略。

案例三：数组交集结果没用集合去重。我最初用列表收集结果，判断if x not in res来去重。对于小数据没问题，但数据量大时x not in res是 O(n)，整体复杂度变成了 O(n*m)。后来改成res.add(x)，既保证了唯一性，又让复杂度降到 O(n)。刷题就是这样，多踩一次坑，印象深一次。

5. 把 Day 6 的经验接到后续题目上

5.1 如何自己判断一道题是不是哈希题

Day 6 结束之后，你要形成一种“条件反射”：看到“是否存在”“是否重复”“唯一结果”“对应关系”“补数”这些信号，第一时间想到哈希表。具体来说，如果一道题你打算用暴力枚举，而枚举的原因是“要找某个匹配的元素”，那大概率可以用哈希表来优化。

比如后续会遇到的赎金信、三数之和、四数之和，它们表面上是数组题、双指针题，但底层都有哈希表的身影。三数之和、四数之和甚至需要“排序 + 双指针”和“哈希表”两种方案同时考虑。所以 Day 6 打下的结构选型能力，会影响你接下来很多天的刷题体验。

5.2 复盘：Day 6 真正应该留下的思维习惯

我自己的体会是，Day 6 最重要的不是 AC 了四道题，而是养成了三个习惯：第一，拿到题先判断数据结构和内存代价；第二，写代码之前明确“键是什么、值是什么”；第三，遇到 O(n²) 解法，主动停下来想想能不能用空间换时间。这三个习惯在后面 day 7、day 8 里会不断放大。

最后再分享一个小技巧：每刷完一组题，不要急着开新题，花十分钟把每道题的核心思路用一句话写在纸上。比如这四道题，我写的是“数组模拟哈希适合定长键”“Set 管存在性”“Map 管关联信息”“边查边存避免覆盖”。哪天你忘了哈希表怎么用，翻到这张纸，几秒钟就能找回手感。这就是 Day 6 真正该留下的东西。