刷完数组和链表之后我第一次真正感受到“数据结构”四个字的分量就是在哈希表这一天。Day5这个专题安排得很实在242题看起来是字符串题实际上在教你用数组手写哈希表349题直接把Set推到台前202题表面是数学游戏核心却是循环检测1题更是各大厂笔试里翻来覆去考的经典模板。这篇就把这四道题一次性讲透顺便把数组、Set、Map三者到底怎么选这件事说明白。适合刚开始学哈希表的同学也适合刷了不少题但总在“用不用哈希、用哪种哈希”上纠结的老手。1. 哈希表基础先搞清楚数组、Set、Map怎么选1.1 什么时候该想到用哈希表哈希表的本质是一个“映射关系”给我一个键我能在接近O(1)的时间里找到对应的值。你不需要关心这个键存不存在一个有序的结构里也不需要去遍历整个集合。日常最典型的场景就是“判断某个元素是否出现过”和“统计某个元素出现的次数”。拿生活打比方你找一本书不需要从书架第一本翻到最后一本而是先去检索系统查索书号再直奔那个位置。哈希表干的就是这个事。刷题的时候只要题干里出现“是否出现过”“是否重复”“统计次数”“找到匹配项”这类字眼第一反应就应该是能不能用哈希表把复杂度降下来。我自己的经验是当你发现自己写了两层循环并且外层循环每个元素都去内层循环“找”什么东西大概率就可以考虑哈希表了。一层遍历负责读数据哈希表负责记忆另一层查找就变成了O(1)级别整体从O(n²)降到O(n)。1.2 数组、Set、Map三种结构的适用场景很多人一听到哈希表就默认等于HashMap。其实在算法题里有三种“哈希思想”的工具合理选择能让时间和空间都省不少。数组是最容易被忽略的哈希表。它本质上就是一个键为“连续下标”的映射表访问任意下标都是O(1)。当你的键是有限范围内的整数或字符用数组做哈希是最快的选择。比如统计26个小写字母的出现次数直接开 int[26]。Set适合“去重”和“判断是否出现过”只用键不需要存值。判断一个元素在不在集合里就是它的主场。Map则不仅需要判断还要把值和键一起存下来比如“元素值→下标”“字符串→出现次数”。三者本质都是哈希结构差别在于数组的下标范围固定且紧凑Set只存键Map存键值对。选择顺序也很清楚如果键能映射成较短的连续下标优先数组如果只关心存在性用Set如果要同时记录额外信息用Map。1.3 哈希冲突和“平均O(1)”的真实含义哈希表能实现O(1)查找前提是哈希函数把不同键均匀映射到不同桶。但不可避免会出现两个键映射到同一个桶这就是哈希冲突。工程上处理冲突常见两种方式拉链法和开放寻址法。标准库里的实现早就把这些封装好了刷算法题时几乎不需要自己写冲突处理。但理解冲突很有用因为它解释了为什么哈希表的O(1)是“平均情况”。极端情况下所有键都冲突查找会退化成O(n)。这也是为什么实际工程里哈希函数的设计和负载因子的控制很重要。刷题时你不用过度担心退化问题但心里要清楚哈希表的强大来自概率平均不是严格保证。2. 242. 有效的字母异位词数组版哈希表入门2.1 题意分析与“异位”的本质题目要求判断两个字符串是否是字母异位词也就是两个字符串中每个字符出现的次数是否完全相同。比如“anagram”和“nagaram”字母种类一样每种字母的个数也一样只是排列顺序不同。这道题最直观的误区是先排序再比较return sorted(s) sorted(t)。代码确实简单但时间复杂度是O(n log n)而且没有体现任何哈希思想。实际上“异位词”的本质是频次统计字符的取值范围又是确定的题目通常限定小写字母这就是典型的数组哈希题。我在第一次做这道题时下意识用了Map统计两个字符串的次数再比较。后来发现用两个Map虽然能过但数组方案明显更干净。键是26个小写字母本身就是连续整数下标根本没有必要引入Map的哈希函数计算和冲突处理成本。2.2 完整解法与代码实现核心思路维护一个长度为26的数组下标对应字母的偏移量。遍历第一个字符串时对应位置加1遍历第二个字符串时对应位置减1。如果最终数组所有位置都是0说明两个字符串的频次完全相同。def isAnagram(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 return all(x 0 for x in count)为什么用ord(ch) - ord(a)而不是直接用ord(ch)因为字母a的ASCII码是97如果直接用它当下标数组需要开到122以上中间97个位置全是浪费。做索引时先减掉基准值让下标从0开始既节省空间也让数组长度和字母表长度一一对应。2.3 几个容易忽略的实现细节第一很多题解会先判断两个字符串长度是否相等。这个剪枝很重要长度不等直接返回False省去后面所有遍历。虽然不判断也不会出错最终数组不会归零但这是一个好的编码习惯。第二如果题目扩展到包含大写字母、数字甚至Unicode字符数组长度就不再是26可能需要扩展到128或256或者干脆改成Map。判断依据还是看键的范围是否紧凑。这也是为什么面试时面试官经常会追问“如果字符集很大怎么办”。第三all(x 0 for x in count)这一步虽然优雅但会额外遍历一次数组。如果追求极致性能可以再加一个计数变量在遍历t的过程中记录“当前非零位置的数量”但数组长度只有26这点性能差异可以忽略。我建议以代码可读性优先。3. 349. 两个数组的交集Set天然自带去重3.1 题目要求与边界条件题目给两个数组要求返回它们的交集且结果中的每个元素必须是唯一的不考虑输出顺序。难点不在“求交集”而在“去重”。比如nums1[1,2,2,1]nums2[2,2]应该返回[2]而不是[2,2]。这道题第一反应是用两层循环判断每个元素是否同时出现在两个数组里然后把匹配到的元素放入结果前再“查重”。这样不仅慢而且逻辑绕你既要判断交集又要判断结果是否已存在代码很容易盘成一团乱麻。其实“去重”这件事Set在结构上就帮你做完了。你不需要额外写条件只要把元素放进Set相同的键只会存一次。整个解法从“两层循环去重判断”降维成“两个Set取交集”。3.2 双Set解法与复杂度分析思路是先把nums1转成Set再去重掉nums1自身的重复元素。然后遍历nums2如果当前元素在Set里出现过说明是交集元素放入结果Set。最后把结果Set转成列表返回。def intersection(nums1, nums2): set1 set(nums1) res_set set() for num in nums2: if num in set1: res_set.add(num) return list(res_set)这里有个关键点遍历的是nums2而不是nums1。因为set1已经从nums1构建好了如果反过来遍历nums1每个元素都需要去set2里查代码相似但逻辑上多了一次set2的构建。差别不大但先构建其中一个集合再用另一个数组做匹配是这类题的通用模板。时间复杂度是O(nm)构建Set是O(n)遍历nums2并查询是O(m)。空间复杂度是O(n)主要消耗在set1上。对于常规题目这个效率已经达标。如果两个数组都很大但内存受限可以改为先排序再用双指针把空间降到O(1)代价是时间升到O(n log n m log m)。这是典型的空间换时间与时间换空间的权衡。3.3 别忽略数据范围的限制有些题解会告诉你因为题目有“数组长度不超过1000元素值范围有限”之类的条件所以可以用数组模拟哈希。但这类“脑筋急转弯”式的优化我建议只在理解原理时做比赛或面试时优先写清晰的双Set版本然后再根据追问优化。我踩过一个坑直接调用语言内建的集合交集方法set(nums1) set(nums2)代码短到离谱。平时刷题这么写没问题但如果是手写代码或者面试最好还是展示出“遍历查询”的过程因为面试官想考察的是你懂不懂哈希表的逻辑而不是你熟不熟悉库函数。当然如果只是自己刷题验证思路内建交集当然可以。4. 202. 快乐数哈希表的另一个用法是判圈4.1 题面里的“数学陷阱”快乐数的定义给定一个正整数每次替换为它各位数字的平方和重复这个过程如果最终能变为1就是快乐数否则会陷入一个不包含1的循环。比如19是快乐数因为19→82→68→100→1。而2不是快乐数因为2→4→16→37→58→89→145→42→20→4开始循环。这道题看起来是数学题实际上考的依然是哈希表。你需要判断的是在变换过程中某个数字是否出现过。如果出现过的数字再次出现说明已经进入循环永远到不了1。这个“出现过的数字再次出现”的判断恰好就是哈希表最擅长的事。我第一次想这道题时试图找数学规律结果发现证明一个数是不是快乐数并不容易。后来意识到根本不需要证明只要检测循环就够了。计算机擅长的是“模拟”而哈希表负责“记住历史”。4.2 set做循环检测的完整代码核心是两步第一步写一个取平方和的辅助函数第二步在主循环里用Set记录所有出现过的数。def get_sum(n): total 0 while n 0: digit n % 10 total digit * digit n // 10 return total def isHappy(n: int) - bool: seen set() while n ! 1 and n not in seen: seen.add(n) n get_sum(n) return n 1get_sum的核心是“取出每一位数”用n % 10拿末位用n // 10去掉末位反复执行直到n变成0。注意这里用整数除法而不是浮点除法否则会出现无限制循环或者类型错误。主循环的终止条件有两个n变成1直接返回Truen已经在seen里出现过说明进入循环返回False。注意循环里先seen.add(n)再更新n顺序不能反。如果把更新放在add之前当前n没有被记录后续循环就检测不到重复。4.3 不用哈希表快慢指针解法哈希表解法已经够用但这里还有一个经典的扩展思路快慢指针也就是弗洛伊德判圈算法。如果数字变化进入了循环那就像在一个环形跑道上跑步快指针迟早会和慢指针相遇。慢指针每次走一步快指针每次走两步如果相遇了且不等于1就说明有循环。def isHappy2(n: int) - bool: slow n fast get_sum(n) while fast ! 1 and slow ! fast: slow get_sum(slow) fast get_sum(get_sum(fast)) return fast 1这个解法的空间复杂度是O(1)不需要Set。它非常优雅但我个人建议初学者先用Set版本因为它更直白地体现了“记录历史→发现重复”的过程。快慢指针本质上是通过不同速度来检测环需要额外理解一层抽象但面试时如果主动说出来会是很大的加分项。5. 1. 两数之和一遍遍历Map的经典套路5.1 暴力法的瓶颈在哪两数之和应该是所有刷题人遇到的第一道“知名”题目。给定一个数组和一个目标值返回两个下标使得对应元素之和等于目标值。最直接的解法是两层循环枚举所有数对判断和是否为目标值。暴力法没有问题但在数组长度很大的时候O(n²)的代价不可接受。假设数组有10万个元素两层循环就是10亿次操作哪怕每步都是常数时间也会明显卡顿。优化的核心就是能不能只遍历一遍就把“我已经见过的数”记下来让后续匹配变成O(1)。这就是经典的“空间换时间”场景。我们需要一个容器保存“元素值→下标”的映射。遍历到当前元素时只需要查一下target - nums[i]在不在这个容器里如果在就找到了答案。这个容器用Map实现。5.2 边查边存的一次遍历解法def twoSum(nums, target): record {} for i, num in enumerate(nums): complement target - num if complement in record: return [record[complement], i] record[num] i return []这里最值得讲的细节是“边查边存”。先查complement是否已在Map里如果不在再把自己存进去。这样设计有一个很重要的原因避免“同一个元素被使用两次”。举个例子nums[3,3]target6。如果先把所有元素插入MapMap中键3对应的下标会被后面的3覆盖成1。遍历到第一个下标0时查6-33会查到下标1结果是对的。但你依赖了“覆盖”这个行为代码的可读性和正确性就变得隐晦。如果用的是不覆盖的写法就可能在i0时查到下标0自己返回[0,0]这是个错误答案。边查边存从逻辑上杜绝了这类问题遍历到下标i时Map里只有下标小于i的元素当前元素还没放进去。这个“先查询后插入”的顺序是这道题最重要的编码习惯。我第一次做的时候先构建了完整的Map再遍历查询虽然也能通过但分析边界情况时特别容易被自己绕晕。改成边查边存后逻辑一目了然。5.3 为什么不存在“更优解”以及变体问题两数之和的O(n)时间复杂度已经是线性下界因为至少要遍历一次数组才能知道有哪些元素。空间上消耗了O(n)用来存储“见过的数”。很多同学会问能不能像有序数组那样用双指针把空间也省了前提是数组要有序。如果先排序时间复杂度是O(n log n)然后双指针可以在O(n)内找到元素但因为排序会改变元素位置返回下标时需要额外记录原始下标反而更麻烦。如果题目要求返回的是元素值而不是下标那排序双指针确实是一个非常优秀的选择空间O(1)。这也是为什么面试官总爱问变体把“返回下标”改成“判断是否存在”解法就完全不同。理解这一点比背模板有用得多。这道题的另一个变体是“两数之和”变成“三数之和”。三数之和不能直接靠一层Map解决因为需要去重和组合多个元素通常用排序双指针。从一数到三难度跳跃不是一点半点但底层逻辑还是“如何高效找出匹配对”。6. 刷题避坑手册哈希表的常见误区与经验6.1 五问五答刷题时的高频纠结点问什么时候一定用数组什么时候一定用Map答没有“一定”只有一个判断标准——键的取值范围是否紧凑且已知。字母异位词的键是26个字母紧密且有限用数组。两数之和的键是数组里的任意整数范围不可控用Map。如果硬用数组你无法用int[-1000000000]这种下标。问Python里in对列表和元组也是O(1)吗答不是。列表和元组用in是线性扫描时间复杂度O(n)。只有Set和Dict的in才是平均O(1)。很多同学代码能跑通但复杂度完全是错的因为不自觉地用了list in list这种写法。判断元素是否在集合里一定要用Set或Dict。问哈希表的键有什么限制答键必须是不可变类型。整数、字符串、元组都可以列表、字典不行。刷题时我经常需要把数组元素组合当键这时要把它转成元组再放进Map。问负数和哈希函数有关系吗答没关系负数作为键很常见。但要注意如果键是负数且你用数组下标模拟就需要做偏移处理比如把所有键加一个偏移量。用Map就不需要关心这个问题。问哈希表查询明明是O(1)为什么感觉有时候比我写两层循环还慢答因为O(1)是平均复杂度常数项不一定小。Map内部要计算哈希值、定位桶、处理冲突每一步都有开销。如果数据量很小比如只有几个元素两层循环反而可能更快。算法分析看的是规模增长趋势不是小数据下的绝对时间。这个认知能帮你避免“为了优化而优化”。6.2 几个提升编码效率的实操习惯第一先想清楚“哈希表的键是什么、值是什么”再动笔。很多人在两数之和里犯迷糊就是因为没想清楚Map存的是值到下标而不是下标到值。先定义好键值关系代码自然就顺了。第二善用辅助函数。快乐数里的get_sum如果直接写在主循环里代码会变得很难读。单独拆一个函数逻辑清晰也方便单测。刷题时经常要反复验证辅助函数对不对拆开后就能快速测试。第三在本地调试时打印中间状态。我第一次做快乐数时调试就是打印n和seen的实时内容很快就能看到循环是怎么形成的。刷题不是在考场上一个字一个字憋代码调试也是一种学习。第四写完代码后走一遍边界测试。空数组、只有一个元素、最大最小值、全重复元素、目标值由前两个元素组成……这些边界能帮你抓住90%的隐藏bug。哈希表相关题目尤其要检查重复元素和键的边界。第五理解内建方法背后的语义但不过度依赖。set(nums1) set(nums2)可以一行搞定349题但你自己手动写一遍“遍历查询”才能真正掌握哈希表在算法里的角色。两件事都做效果最好。我在实际刷哈希表专题时最大的体会是不要死记“这是Set题”“这是Map题”而是问自己三个问题——我要查什么东西查一次要花多少时间能不能用已经读到的数据减少后续查询的成本想通这三个问题哈希表基本就出师了。Day5这四道题从数组哈希到Set去重再到循环检测和Map配对正好覆盖了哈希表的全部典型用法。把它们吃透后面做滑动窗口、前缀和、频率统计这些题时你会发现自己已经多了一层“条件反射”。
刷完数组和链表之后我第一次真正感受到“数据结构”四个字的分量就是在哈希表这一天。Day5这个专题安排得很实在242题看起来是字符串题实际上在教你用数组手写哈希表349题直接把Set推到台前202题表面是数学游戏核心却是循环检测1题更是各大厂笔试里翻来覆去考的经典模板。这篇就把这四道题一次性讲透顺便把数组、Set、Map三者到底怎么选这件事说明白。适合刚开始学哈希表的同学也适合刷了不少题但总在“用不用哈希、用哪种哈希”上纠结的老手。1. 哈希表基础先搞清楚数组、Set、Map怎么选1.1 什么时候该想到用哈希表哈希表的本质是一个“映射关系”给我一个键我能在接近O(1)的时间里找到对应的值。你不需要关心这个键存不存在一个有序的结构里也不需要去遍历整个集合。日常最典型的场景就是“判断某个元素是否出现过”和“统计某个元素出现的次数”。拿生活打比方你找一本书不需要从书架第一本翻到最后一本而是先去检索系统查索书号再直奔那个位置。哈希表干的就是这个事。刷题的时候只要题干里出现“是否出现过”“是否重复”“统计次数”“找到匹配项”这类字眼第一反应就应该是能不能用哈希表把复杂度降下来。我自己的经验是当你发现自己写了两层循环并且外层循环每个元素都去内层循环“找”什么东西大概率就可以考虑哈希表了。一层遍历负责读数据哈希表负责记忆另一层查找就变成了O(1)级别整体从O(n²)降到O(n)。1.2 数组、Set、Map三种结构的适用场景很多人一听到哈希表就默认等于HashMap。其实在算法题里有三种“哈希思想”的工具合理选择能让时间和空间都省不少。数组是最容易被忽略的哈希表。它本质上就是一个键为“连续下标”的映射表访问任意下标都是O(1)。当你的键是有限范围内的整数或字符用数组做哈希是最快的选择。比如统计26个小写字母的出现次数直接开 int[26]。Set适合“去重”和“判断是否出现过”只用键不需要存值。判断一个元素在不在集合里就是它的主场。Map则不仅需要判断还要把值和键一起存下来比如“元素值→下标”“字符串→出现次数”。三者本质都是哈希结构差别在于数组的下标范围固定且紧凑Set只存键Map存键值对。选择顺序也很清楚如果键能映射成较短的连续下标优先数组如果只关心存在性用Set如果要同时记录额外信息用Map。1.3 哈希冲突和“平均O(1)”的真实含义哈希表能实现O(1)查找前提是哈希函数把不同键均匀映射到不同桶。但不可避免会出现两个键映射到同一个桶这就是哈希冲突。工程上处理冲突常见两种方式拉链法和开放寻址法。标准库里的实现早就把这些封装好了刷算法题时几乎不需要自己写冲突处理。但理解冲突很有用因为它解释了为什么哈希表的O(1)是“平均情况”。极端情况下所有键都冲突查找会退化成O(n)。这也是为什么实际工程里哈希函数的设计和负载因子的控制很重要。刷题时你不用过度担心退化问题但心里要清楚哈希表的强大来自概率平均不是严格保证。2. 242. 有效的字母异位词数组版哈希表入门2.1 题意分析与“异位”的本质题目要求判断两个字符串是否是字母异位词也就是两个字符串中每个字符出现的次数是否完全相同。比如“anagram”和“nagaram”字母种类一样每种字母的个数也一样只是排列顺序不同。这道题最直观的误区是先排序再比较return sorted(s) sorted(t)。代码确实简单但时间复杂度是O(n log n)而且没有体现任何哈希思想。实际上“异位词”的本质是频次统计字符的取值范围又是确定的题目通常限定小写字母这就是典型的数组哈希题。我在第一次做这道题时下意识用了Map统计两个字符串的次数再比较。后来发现用两个Map虽然能过但数组方案明显更干净。键是26个小写字母本身就是连续整数下标根本没有必要引入Map的哈希函数计算和冲突处理成本。2.2 完整解法与代码实现核心思路维护一个长度为26的数组下标对应字母的偏移量。遍历第一个字符串时对应位置加1遍历第二个字符串时对应位置减1。如果最终数组所有位置都是0说明两个字符串的频次完全相同。def isAnagram(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 return all(x 0 for x in count)为什么用ord(ch) - ord(a)而不是直接用ord(ch)因为字母a的ASCII码是97如果直接用它当下标数组需要开到122以上中间97个位置全是浪费。做索引时先减掉基准值让下标从0开始既节省空间也让数组长度和字母表长度一一对应。2.3 几个容易忽略的实现细节第一很多题解会先判断两个字符串长度是否相等。这个剪枝很重要长度不等直接返回False省去后面所有遍历。虽然不判断也不会出错最终数组不会归零但这是一个好的编码习惯。第二如果题目扩展到包含大写字母、数字甚至Unicode字符数组长度就不再是26可能需要扩展到128或256或者干脆改成Map。判断依据还是看键的范围是否紧凑。这也是为什么面试时面试官经常会追问“如果字符集很大怎么办”。第三all(x 0 for x in count)这一步虽然优雅但会额外遍历一次数组。如果追求极致性能可以再加一个计数变量在遍历t的过程中记录“当前非零位置的数量”但数组长度只有26这点性能差异可以忽略。我建议以代码可读性优先。3. 349. 两个数组的交集Set天然自带去重3.1 题目要求与边界条件题目给两个数组要求返回它们的交集且结果中的每个元素必须是唯一的不考虑输出顺序。难点不在“求交集”而在“去重”。比如nums1[1,2,2,1]nums2[2,2]应该返回[2]而不是[2,2]。这道题第一反应是用两层循环判断每个元素是否同时出现在两个数组里然后把匹配到的元素放入结果前再“查重”。这样不仅慢而且逻辑绕你既要判断交集又要判断结果是否已存在代码很容易盘成一团乱麻。其实“去重”这件事Set在结构上就帮你做完了。你不需要额外写条件只要把元素放进Set相同的键只会存一次。整个解法从“两层循环去重判断”降维成“两个Set取交集”。3.2 双Set解法与复杂度分析思路是先把nums1转成Set再去重掉nums1自身的重复元素。然后遍历nums2如果当前元素在Set里出现过说明是交集元素放入结果Set。最后把结果Set转成列表返回。def intersection(nums1, nums2): set1 set(nums1) res_set set() for num in nums2: if num in set1: res_set.add(num) return list(res_set)这里有个关键点遍历的是nums2而不是nums1。因为set1已经从nums1构建好了如果反过来遍历nums1每个元素都需要去set2里查代码相似但逻辑上多了一次set2的构建。差别不大但先构建其中一个集合再用另一个数组做匹配是这类题的通用模板。时间复杂度是O(nm)构建Set是O(n)遍历nums2并查询是O(m)。空间复杂度是O(n)主要消耗在set1上。对于常规题目这个效率已经达标。如果两个数组都很大但内存受限可以改为先排序再用双指针把空间降到O(1)代价是时间升到O(n log n m log m)。这是典型的空间换时间与时间换空间的权衡。3.3 别忽略数据范围的限制有些题解会告诉你因为题目有“数组长度不超过1000元素值范围有限”之类的条件所以可以用数组模拟哈希。但这类“脑筋急转弯”式的优化我建议只在理解原理时做比赛或面试时优先写清晰的双Set版本然后再根据追问优化。我踩过一个坑直接调用语言内建的集合交集方法set(nums1) set(nums2)代码短到离谱。平时刷题这么写没问题但如果是手写代码或者面试最好还是展示出“遍历查询”的过程因为面试官想考察的是你懂不懂哈希表的逻辑而不是你熟不熟悉库函数。当然如果只是自己刷题验证思路内建交集当然可以。4. 202. 快乐数哈希表的另一个用法是判圈4.1 题面里的“数学陷阱”快乐数的定义给定一个正整数每次替换为它各位数字的平方和重复这个过程如果最终能变为1就是快乐数否则会陷入一个不包含1的循环。比如19是快乐数因为19→82→68→100→1。而2不是快乐数因为2→4→16→37→58→89→145→42→20→4开始循环。这道题看起来是数学题实际上考的依然是哈希表。你需要判断的是在变换过程中某个数字是否出现过。如果出现过的数字再次出现说明已经进入循环永远到不了1。这个“出现过的数字再次出现”的判断恰好就是哈希表最擅长的事。我第一次想这道题时试图找数学规律结果发现证明一个数是不是快乐数并不容易。后来意识到根本不需要证明只要检测循环就够了。计算机擅长的是“模拟”而哈希表负责“记住历史”。4.2 set做循环检测的完整代码核心是两步第一步写一个取平方和的辅助函数第二步在主循环里用Set记录所有出现过的数。def get_sum(n): total 0 while n 0: digit n % 10 total digit * digit n // 10 return total def isHappy(n: int) - bool: seen set() while n ! 1 and n not in seen: seen.add(n) n get_sum(n) return n 1get_sum的核心是“取出每一位数”用n % 10拿末位用n // 10去掉末位反复执行直到n变成0。注意这里用整数除法而不是浮点除法否则会出现无限制循环或者类型错误。主循环的终止条件有两个n变成1直接返回Truen已经在seen里出现过说明进入循环返回False。注意循环里先seen.add(n)再更新n顺序不能反。如果把更新放在add之前当前n没有被记录后续循环就检测不到重复。4.3 不用哈希表快慢指针解法哈希表解法已经够用但这里还有一个经典的扩展思路快慢指针也就是弗洛伊德判圈算法。如果数字变化进入了循环那就像在一个环形跑道上跑步快指针迟早会和慢指针相遇。慢指针每次走一步快指针每次走两步如果相遇了且不等于1就说明有循环。def isHappy2(n: int) - bool: slow n fast get_sum(n) while fast ! 1 and slow ! fast: slow get_sum(slow) fast get_sum(get_sum(fast)) return fast 1这个解法的空间复杂度是O(1)不需要Set。它非常优雅但我个人建议初学者先用Set版本因为它更直白地体现了“记录历史→发现重复”的过程。快慢指针本质上是通过不同速度来检测环需要额外理解一层抽象但面试时如果主动说出来会是很大的加分项。5. 1. 两数之和一遍遍历Map的经典套路5.1 暴力法的瓶颈在哪两数之和应该是所有刷题人遇到的第一道“知名”题目。给定一个数组和一个目标值返回两个下标使得对应元素之和等于目标值。最直接的解法是两层循环枚举所有数对判断和是否为目标值。暴力法没有问题但在数组长度很大的时候O(n²)的代价不可接受。假设数组有10万个元素两层循环就是10亿次操作哪怕每步都是常数时间也会明显卡顿。优化的核心就是能不能只遍历一遍就把“我已经见过的数”记下来让后续匹配变成O(1)。这就是经典的“空间换时间”场景。我们需要一个容器保存“元素值→下标”的映射。遍历到当前元素时只需要查一下target - nums[i]在不在这个容器里如果在就找到了答案。这个容器用Map实现。5.2 边查边存的一次遍历解法def twoSum(nums, target): record {} for i, num in enumerate(nums): complement target - num if complement in record: return [record[complement], i] record[num] i return []这里最值得讲的细节是“边查边存”。先查complement是否已在Map里如果不在再把自己存进去。这样设计有一个很重要的原因避免“同一个元素被使用两次”。举个例子nums[3,3]target6。如果先把所有元素插入MapMap中键3对应的下标会被后面的3覆盖成1。遍历到第一个下标0时查6-33会查到下标1结果是对的。但你依赖了“覆盖”这个行为代码的可读性和正确性就变得隐晦。如果用的是不覆盖的写法就可能在i0时查到下标0自己返回[0,0]这是个错误答案。边查边存从逻辑上杜绝了这类问题遍历到下标i时Map里只有下标小于i的元素当前元素还没放进去。这个“先查询后插入”的顺序是这道题最重要的编码习惯。我第一次做的时候先构建了完整的Map再遍历查询虽然也能通过但分析边界情况时特别容易被自己绕晕。改成边查边存后逻辑一目了然。5.3 为什么不存在“更优解”以及变体问题两数之和的O(n)时间复杂度已经是线性下界因为至少要遍历一次数组才能知道有哪些元素。空间上消耗了O(n)用来存储“见过的数”。很多同学会问能不能像有序数组那样用双指针把空间也省了前提是数组要有序。如果先排序时间复杂度是O(n log n)然后双指针可以在O(n)内找到元素但因为排序会改变元素位置返回下标时需要额外记录原始下标反而更麻烦。如果题目要求返回的是元素值而不是下标那排序双指针确实是一个非常优秀的选择空间O(1)。这也是为什么面试官总爱问变体把“返回下标”改成“判断是否存在”解法就完全不同。理解这一点比背模板有用得多。这道题的另一个变体是“两数之和”变成“三数之和”。三数之和不能直接靠一层Map解决因为需要去重和组合多个元素通常用排序双指针。从一数到三难度跳跃不是一点半点但底层逻辑还是“如何高效找出匹配对”。6. 刷题避坑手册哈希表的常见误区与经验6.1 五问五答刷题时的高频纠结点问什么时候一定用数组什么时候一定用Map答没有“一定”只有一个判断标准——键的取值范围是否紧凑且已知。字母异位词的键是26个字母紧密且有限用数组。两数之和的键是数组里的任意整数范围不可控用Map。如果硬用数组你无法用int[-1000000000]这种下标。问Python里in对列表和元组也是O(1)吗答不是。列表和元组用in是线性扫描时间复杂度O(n)。只有Set和Dict的in才是平均O(1)。很多同学代码能跑通但复杂度完全是错的因为不自觉地用了list in list这种写法。判断元素是否在集合里一定要用Set或Dict。问哈希表的键有什么限制答键必须是不可变类型。整数、字符串、元组都可以列表、字典不行。刷题时我经常需要把数组元素组合当键这时要把它转成元组再放进Map。问负数和哈希函数有关系吗答没关系负数作为键很常见。但要注意如果键是负数且你用数组下标模拟就需要做偏移处理比如把所有键加一个偏移量。用Map就不需要关心这个问题。问哈希表查询明明是O(1)为什么感觉有时候比我写两层循环还慢答因为O(1)是平均复杂度常数项不一定小。Map内部要计算哈希值、定位桶、处理冲突每一步都有开销。如果数据量很小比如只有几个元素两层循环反而可能更快。算法分析看的是规模增长趋势不是小数据下的绝对时间。这个认知能帮你避免“为了优化而优化”。6.2 几个提升编码效率的实操习惯第一先想清楚“哈希表的键是什么、值是什么”再动笔。很多人在两数之和里犯迷糊就是因为没想清楚Map存的是值到下标而不是下标到值。先定义好键值关系代码自然就顺了。第二善用辅助函数。快乐数里的get_sum如果直接写在主循环里代码会变得很难读。单独拆一个函数逻辑清晰也方便单测。刷题时经常要反复验证辅助函数对不对拆开后就能快速测试。第三在本地调试时打印中间状态。我第一次做快乐数时调试就是打印n和seen的实时内容很快就能看到循环是怎么形成的。刷题不是在考场上一个字一个字憋代码调试也是一种学习。第四写完代码后走一遍边界测试。空数组、只有一个元素、最大最小值、全重复元素、目标值由前两个元素组成……这些边界能帮你抓住90%的隐藏bug。哈希表相关题目尤其要检查重复元素和键的边界。第五理解内建方法背后的语义但不过度依赖。set(nums1) set(nums2)可以一行搞定349题但你自己手动写一遍“遍历查询”才能真正掌握哈希表在算法里的角色。两件事都做效果最好。我在实际刷哈希表专题时最大的体会是不要死记“这是Set题”“这是Map题”而是问自己三个问题——我要查什么东西查一次要花多少时间能不能用已经读到的数据减少后续查询的成本想通这三个问题哈希表基本就出师了。Day5这四道题从数组哈希到Set去重再到循环检测和Map配对正好覆盖了哈希表的全部典型用法。把它们吃透后面做滑动窗口、前缀和、频率统计这些题时你会发现自己已经多了一层“条件反射”。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
