代码随想录算法训练营第六天的打卡笔记来了。今天主题是哈希表涉及四道经典题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三者的使用场景对比这是今天最重要的部分。刷哈希表专题代码往往不复杂真正的难点是第一步拿到题目后该用哪个结构我总结了一套判断逻辑一刷时我经常靠猜二刷后基本能稳定套用结构核心能力典型用法适用场景数组下标即键值是计数或标记int[26] 记录字母出现次数数据范围小而连续比如小写字母、有限的数字范围Set只记录“存在/不存在”自动去重HashSet 判断元素是否出现过判重、求交集、去重Map记录键值对值可以统计次数或保存下标HashMap值, 次数/下标需要根据一个键查到额外信息时举个例子你就明白了。要统计一句话里每个英文字母出现的次数字母只有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 anagramt 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题会写MapCharacter, Integer功能上没错但完全没有必要。数组下标天然就是字符编码用数组不仅更简洁还避免了HashMap的哈希计算和装箱开销。做算法题不是写业务代码能用轻量结构就不要上重量级结构。第二这个题是后面很多字符串哈希题的“祖宗”。比如49题字母异位词分组可以把每个单词的频率数组转成字符串作为key438题找到字符串中所有字母异位词要用滑动窗口加频率数组。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]如果不加结果Set2会被收集三次最终输出就错了。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]; } SetInteger set1 new HashSet(); for (int num : nums1) { set1.add(num); } SetInteger 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(nm)空间复杂度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; } ListInteger 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(nm)但空间上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。比如191^2 9^2 828^2 2^2 686^2 8^2 1001^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) { SetInteger 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 22 - 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从i1到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) { MapInteger, 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题明明数组就够我非得写个MapCharacter, Integer代码又长又难读。二刷后才明白先看数据范围再决定用什么结构是哈希专题的第一步。第二349题忘了去重。用Set存了nums1遍历nums2时一发现存在就直接加到结果数组结果输出了一堆重复值。后来才想到要用第二个Set或者像数组标记法那样收集后立刻置false。第三202题没有主动想到用Set判循环。我当时的想法是“这题是不是要用数学推导证明什么”完全跑偏了。实际上就是用哈希记住出现过的数遇到重复就说明死循环。第四1题搞反了先放再查的顺序。这个坑我上面已经详细解释过[3,3]这个测试用例能精准命中。一刷时我甚至没意识到这个顺序问题只是AC了就没想太多直到二刷手动推用例才发现。6.2 二刷后我总结的哈希表做题模板二刷之后我给自己整理了一套做题顺序分享给你先读题确认数据范围。数字范围小且连续优先想数组范围大或类型是字符串、对象再想Set或Map。再想清楚需要什么信息。只需要判断存在用Set需要保存下标或次数用Map需要用下标当键用数组。最后才写代码。写完手动跑一个简单测试用例尤其检查会不会重复使用同一元素、会不会重复收集结果、有没有环路风险。今天四道题可以用一张表串起来题目核心考点选择的结构主要陷阱242. 有效的字母异位词字符频率统计数组 int[26]忘了先判断长度349. 两个数组的交集判重与去重Set / boolean数组结果重复202. 快乐数用哈希判状态循环HashSet没意识到非快乐数必成环1. 两数之和空间换时间HashMap先放再查导致下标重复6.3 关于Java哈希表输出的几个小经验因为我是用Java刷题的这里单独说几个Java哈希表输出相关的经验也是二刷时注意到的。第一HashMap和HashSet的遍历顺序不稳定。今天349题用Set收集结果后直接转数组每次提交返回的顺序可能都不一样。题目不要求顺序所以没事但如果你在本地调试时发现输出顺序跟自己想的不一样不要怀疑算法错了先看题目是否要求顺序。第二HashMap的键如果是Integer注意自动装箱。比如map.containsKey(complement)时complement是int会自动装箱成IntegerJava的Integer缓存只在-128到127之间生效超过这个范围就是不同对象了但HashMap内部用的equals比较所以不用担心Integer的equals比较的是值。第三如果想让输出有序可以考虑TreeSet或者TreeMap。不过大多数算法题不要求有序用TreeSet反而多一个O(log n)的插入成本没必要。6.4 关于复习节奏的一点建议训练营的节奏很快第六天已经进入第二个专题。我的体会是每天的新题要认真做但隔两三天一定要回头把前面的题重新手写一遍。比如今天这四道题一周后再写一次别看好几篇题解直接凭记忆和思路写。能一次性通过才是真正掌握了。我在二刷时给自己定的标准是每道题不仅能写出代码还要能说清楚“为什么这么做”。比如242为什么用数组而不用Map349为什么要第二个Set去重202为什么一定会进入循环1为什么必须先进Map查再放。这些“为什么”才是面试时真正会被问到的。今天这四道题全部过完哈希表这个专题算是在我心里真正立住了。我个人最大的体会是哈希表不难难的是想清楚“我把什么当key、把什么当value、用什么结构当容器”。这是需要靠做题量喂出来的感觉不是看一两篇题解就能会的。最后再分享一个小技巧刷题时遇到重复出现、快速查找、状态循环这类字眼先别急着写代码停下来问自己一句“值域有多大”。如果值域小到能用数组就别让HashMap折腾你自己了。希望这篇二刷笔记能帮你在哈希表这个专题上少走点弯路明天继续。Good luck and enjoy! 哈希表专题：数组、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三者的使用场景对比这是今天最重要的部分。刷哈希表专题代码往往不复杂真正的难点是第一步拿到题目后该用哪个结构我总结了一套判断逻辑一刷时我经常靠猜二刷后基本能稳定套用结构核心能力典型用法适用场景数组下标即键值是计数或标记int[26] 记录字母出现次数数据范围小而连续比如小写字母、有限的数字范围Set只记录“存在/不存在”自动去重HashSet 判断元素是否出现过判重、求交集、去重Map记录键值对值可以统计次数或保存下标HashMap值, 次数/下标需要根据一个键查到额外信息时举个例子你就明白了。要统计一句话里每个英文字母出现的次数字母只有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 anagramt 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题会写MapCharacter, Integer功能上没错但完全没有必要。数组下标天然就是字符编码用数组不仅更简洁还避免了HashMap的哈希计算和装箱开销。做算法题不是写业务代码能用轻量结构就不要上重量级结构。第二这个题是后面很多字符串哈希题的“祖宗”。比如49题字母异位词分组可以把每个单词的频率数组转成字符串作为key438题找到字符串中所有字母异位词要用滑动窗口加频率数组。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]如果不加结果Set2会被收集三次最终输出就错了。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]; } SetInteger set1 new HashSet(); for (int num : nums1) { set1.add(num); } SetInteger 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(nm)空间复杂度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; } ListInteger 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(nm)但空间上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。比如191^2 9^2 828^2 2^2 686^2 8^2 1001^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) { SetInteger 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 22 - 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从i1到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) { MapInteger, 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题明明数组就够我非得写个MapCharacter, Integer代码又长又难读。二刷后才明白先看数据范围再决定用什么结构是哈希专题的第一步。第二349题忘了去重。用Set存了nums1遍历nums2时一发现存在就直接加到结果数组结果输出了一堆重复值。后来才想到要用第二个Set或者像数组标记法那样收集后立刻置false。第三202题没有主动想到用Set判循环。我当时的想法是“这题是不是要用数学推导证明什么”完全跑偏了。实际上就是用哈希记住出现过的数遇到重复就说明死循环。第四1题搞反了先放再查的顺序。这个坑我上面已经详细解释过[3,3]这个测试用例能精准命中。一刷时我甚至没意识到这个顺序问题只是AC了就没想太多直到二刷手动推用例才发现。6.2 二刷后我总结的哈希表做题模板二刷之后我给自己整理了一套做题顺序分享给你先读题确认数据范围。数字范围小且连续优先想数组范围大或类型是字符串、对象再想Set或Map。再想清楚需要什么信息。只需要判断存在用Set需要保存下标或次数用Map需要用下标当键用数组。最后才写代码。写完手动跑一个简单测试用例尤其检查会不会重复使用同一元素、会不会重复收集结果、有没有环路风险。今天四道题可以用一张表串起来题目核心考点选择的结构主要陷阱242. 有效的字母异位词字符频率统计数组 int[26]忘了先判断长度349. 两个数组的交集判重与去重Set / boolean数组结果重复202. 快乐数用哈希判状态循环HashSet没意识到非快乐数必成环1. 两数之和空间换时间HashMap先放再查导致下标重复6.3 关于Java哈希表输出的几个小经验因为我是用Java刷题的这里单独说几个Java哈希表输出相关的经验也是二刷时注意到的。第一HashMap和HashSet的遍历顺序不稳定。今天349题用Set收集结果后直接转数组每次提交返回的顺序可能都不一样。题目不要求顺序所以没事但如果你在本地调试时发现输出顺序跟自己想的不一样不要怀疑算法错了先看题目是否要求顺序。第二HashMap的键如果是Integer注意自动装箱。比如map.containsKey(complement)时complement是int会自动装箱成IntegerJava的Integer缓存只在-128到127之间生效超过这个范围就是不同对象了但HashMap内部用的equals比较所以不用担心Integer的equals比较的是值。第三如果想让输出有序可以考虑TreeSet或者TreeMap。不过大多数算法题不要求有序用TreeSet反而多一个O(log n)的插入成本没必要。6.4 关于复习节奏的一点建议训练营的节奏很快第六天已经进入第二个专题。我的体会是每天的新题要认真做但隔两三天一定要回头把前面的题重新手写一遍。比如今天这四道题一周后再写一次别看好几篇题解直接凭记忆和思路写。能一次性通过才是真正掌握了。我在二刷时给自己定的标准是每道题不仅能写出代码还要能说清楚“为什么这么做”。比如242为什么用数组而不用Map349为什么要第二个Set去重202为什么一定会进入循环1为什么必须先进Map查再放。这些“为什么”才是面试时真正会被问到的。今天这四道题全部过完哈希表这个专题算是在我心里真正立住了。我个人最大的体会是哈希表不难难的是想清楚“我把什么当key、把什么当value、用什么结构当容器”。这是需要靠做题量喂出来的感觉不是看一两篇题解就能会的。最后再分享一个小技巧刷题时遇到重复出现、快速查找、状态循环这类字眼先别急着写代码停下来问自己一句“值域有多大”。如果值域小到能用数组就别让HashMap折腾你自己了。希望这篇二刷笔记能帮你在哈希表这个专题上少走点弯路明天继续。Good luck and enjoy!