代码随想录刷到Day05正好进入哈希表这个专题。说实话这一天的内容算是我刷题过程中的一个小转折点前几天的二分查找、双指针、滑动窗口套路都相对固定到了哈希表这里就开始考验你能不能从“暴力遍历”的思维里跳出来了。我自己刚开始刷题的时候觉得哈希表不就是会用HashSet和HashMap嘛真到面试被问到“这题为什么用数组不用set”一下子就卡住了。所以Day05的几道题看起来基础但里面的选型逻辑和边界处理才是真正拉开差距的地方。这篇文章就围绕Day05的几道经典题展开适合正在按代码随想录打卡表刷题的人也适合那些LeetCode刷了不少、但遇到哈希相关题目还是“凭感觉”选数据结构的朋友。我会把哈希表的底层逻辑、四道题完整拆解、以及我自己踩过的坑一次说清楚最后再聊聊怎么把这种思维用到后面的题目里。1. 哈希表专题为什么会在第五天出现1.1 前四天练的是“顺序思维”第五天开始换挡代码随想录的打卡表前面几天基本都是数组、链表这些东西解题思路偏线性要么是遍历要么是双指针要么是快慢指针。这些题目的核心是“怎么把数据排好序、怎么在有序结构里做查找”。而哈希表一上来就换了一种玩法——它不要求数据有序也不需要维护索引它靠的是“直接映射”。这种切换很多新人刚开始很不适应。比如给你一个字符串让你判断两个字符串是不是字母异位词前四天学到的那些技巧好像都用不太上。这时候就需要意识到一个问题当我们需要快速判断“某个元素在不在集合里”时顺序遍历是O(n)的开销而哈希表是O(1)的开销。这个思考方式的转变其实就是从“顺序思维”切到“查找思维”。我印象特别深当时我刷Day05之前自己先试着做两数之和第一反应是两层for循环提交之后虽然AC了但看到耗时很不舒服。后来才明白暴力解的问题不仅在复杂度上更在于你压根没有建立“空间换时间”的直觉。代码随想录把哈希表放在第五天其实就是想让你尽早建立这种直觉越早越好。1.2 这个专题真正要练的能力哈希表专题真正要练的不是记住HashMap怎么用而是三个能力第一个是选型能力。拿到一道题能判断出用数组、HashSet还是HashMap并且能说出理由。数组可能在O(1)时间比哈希表还快因为它不需要计算哈希值也不需要处理哈希冲突。第二个是空间复杂度的意识。哈希表本质上是空间换时间面试里经常要你回答用多少额外空间。第三个是边界控制能力。哈希表的很多坑比如重复元素、负数、空输入、Integer的装箱相等问题全都在边界里。所以Day05这几道题题目本身不难但它们是很好的训练载体。如果只满足于“把题AC了”那确实有点浪费如果能把每一道题的选型理由、复杂度、边界情况都盘一遍这一天的收获其实比后面很多难的题目都要大。2. 先搞懂哈希表的底层再谈刷题2.1 哈希函数、冲突与两种经典解决思路哈希表的底层原理并不复杂简单说它把要存储的元素通过一个哈希函数计算出一个位置然后直接存到数组的这个位置上。这样查找的时候只需要重新计算哈希值就能直接在数组的对应位置把数据取出来所以平均时间复杂度是O(1)。问题是哈希函数不可能是完美的一一映射。不同元素算出来可能落在同一个位置这种情况叫哈希冲突。解决冲突有两大流派开放定址法和链地址法。开放定址法就是位置被占了之后按某种规则继续往后找空位比如线性探测、二次探测链地址法则是每个槽位挂一个链表冲突的元素串在一起Java的HashMap在链表过长时还会把链表转成红黑树本质上也是链地址法的一种优化。我之前一直不理解为什么会有这么多细节直到有一次线下分享一个朋友用了个特别贴切的比喻哈希表就像一栋楼哈希函数决定你住哪一层但同一层可能住了很多人这时候要么换楼层开放定址法要么同一层多摆几间房链地址法。这么一想原理就通了。对刷题来说我们不需要真的实现红黑树但搞清楚冲突是怎么解决的能帮你想清楚为什么哈希表是“平均O(1)、最坏O(n)”。2.2 数组、Set、Map到底怎么选这是哈希表专题最核心的问题也是面试官最爱追着问的点。三种结构各有适用场景我的判断标准是这样的首先看key的取值范围。如果key是小范围的整数或者字符这种连续结构优先用数组。比如判断字母异位词字符一共26个你直接开一个长度为26的int数组用字符减a作为索引这天然就是一个哈希表。数组连哈希函数都不用算因为索引本身就是映射而且绝对没有冲突性能是最好的。其次看需求。如果只需要判断“元素有没有出现过”用HashSet就够了如果需要“元素到另一个信息”的映射比如元素到下标、元素到次数那就用HashMap。这个判断非常直接不要一上来就HashMap很多题用Set更轻量。最后还要看数据的密度。如果数据稀疏比如取值范围很大但实际元素很少用数组就浪费了但如果取值范围小又密集数组的空间消耗也很小。举个例子给你10000个可能出现的数但实际只有5个那你开10000长度的数组就有点傻了HashSet就合适。反之如果数字范围限定在0到100数组就一定是最优选。2.3 Java里HashMap和HashSet底层要了解哪些用Java刷题的话底层有一些细节是躲不开的。HashSet内部其实就是一个HashMap只不过它只用到keyvalue是一个固定的ObjectHashSet的add操作实际上就是在map里put(key, PRESENT)。理解这层关系你会发现两个结构的使用场景其实是一体的。另外一个高频考点是哈希值的计算。Java的String.hashCode()用的是31作为乘数为什么是31因为31是奇素数并且编译器会对31做优化31*h可以写成(h5)-h性能更好。奇素数能减少乘法溢出后信息的丢失冲突概率相对低。这个细节不一定在Day05直接考到但面试聊到HashMap的哈希函数时能说出31的原因是加分项。还有一点要注意Java 8之后HashMap在链表长度超过阈值时会树化链表长度超过8、数组容量超过64时会把链表转成红黑树。刷题时我们一般不关心这个但如果你在面试里聊HashMap的优化顺手提到这个阈值能显得你对底层是有研究的。3. 四道题逐题拆解3.1 242 有效字母异位词数组才是最省的哈希表题目很简单给定两个字符串s和t判断它们是不是字母异位词就是组成字母相同、顺序不同。这道题在有哈希表概念之前最常见的操作是先排序再比较但排序的时间复杂度是O(n log n)。用哈希表思路我们可以统计字符出现次数然后对比。代码随想录给的思路很干净因为只涉及小写字母直接申请一个长度26的int数组。先遍历第一个字符串每个字符出现对应索引加一再遍历第二个字符串出现对应索引减一最后检查数组里是不是全是0。class Solution { 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; } }这里有两个关键点值得展开。第一为什么不用HashMap因为在字符集固定且数量少的前提下数组查找是直接寻址速度比HashMap快不少。虽然都是O(1)但常数不一样刷题可能看不出差别面试一定要讲出来。第二索引为什么要减a因为char底层是数字a的ASCII码是97如果不减数组就得开到很大减了之后a对应0z对应25刚好26个位置。进阶思考如果字符串包含Unicode字符怎么办比如中文、emoji。这时候数组就不行了因为字符范围太大应该换成Mapkey是字符value是次数。这也是很多面试官喜欢追问的变体基础解法加上扩展思考才是完整的回答。3.2 349 两个数组的交集去重直接用Set第二道题是计算两个数组的交集要求结果里每个元素唯一。这题很自然地想到Set先把第一个数组的所有元素放进一个Set再遍历第二个数组如果Set里有这个元素就加入结果Set最后把结果Set转成数组。我第一遍做的时候在“用两个Set还是用一个Set”上纠结了一下。后来看到代码随想录的思路才明白一个Set做查找表一个Set做结果集就够了。查找表的Set负责去重和O(1)查找结果集的Set负责给结果去重两个各司其职。class Solution { public int[] intersection(int[] nums1, int[] nums2) { SetInteger table new HashSet(); for (int num : nums1) { table.add(num); } SetInteger resultSet new HashSet(); for (int num : nums2) { if (table.contains(num)) { resultSet.add(num); } } int[] result new int[resultSet.size()]; int index 0; for (int num : resultSet) { result[index] num; } return result; } }这题值得思考的是为什么不用数组因为题目里nums的值没有限制取值范围可能是负数也可能很大。开数组的话要么开不下要么需要做偏移转换非常别扭。Set天生就是为这种场景准备的我只关心“在不在”不关心“在哪”。复杂度上设两个数组长度分别是m和n时间复杂度是O(mn)空间复杂度是O(min(m,n))。如果你用较小的数组做查找表遍历大的数组去查空间还能更省一点。这是一个很小的优化点但面试时提出来很加分。3.3 202 快乐数题眼是判断循环快乐数这题我第一次做的时候完全没意识到这是一个哈希表题。题目说一个数不断把每一位的平方相加如果能变成1就是快乐数否则会陷入循环。看到“循环”两个字第一反应可能是快慢指针但哈希表的思路更直观用一个Set记录每一步出现过的数如果新算出来的数已经在Set里出现过说明进入了循环直接返回false。以19为例19拆成1和9平方和是82然后是68再到100最后到1所以19是快乐数。整个过程里如果某个和之前出现过了根据数学性质后面一定会无限循环但不一定回到开头那个数。核心代码非常短class Solution { public boolean isHappy(int n) { SetInteger seen new HashSet(); while (n ! 1 !seen.contains(n)) { seen.add(n); int sum 0; while (n 0) { int digit n % 10; sum digit * digit; n / 10; } n sum; } return n 1; } }这个题的题眼就是“用Set记录历史”。很多新手想当然地写一个while循环判断条件里没有Set结果死循环跑不出去。我当时看到测试用例一直超时才意识到自己根本没处理循环情况。这题的启发是题目说“不是快乐数会无限循环”其实是在提示你需要判断重复。看到“重复”和“循环”就要条件反射地想到哈希表或者快慢指针。还有一个可以聊的扩展点这题不用Set也能做用弗洛伊德判圈算法也就是快慢指针。空间复杂度可以从O(logn)降到O(1)。面试时答完哈希表解法之后补一句“还可以用快慢指针把空间降到O(1)”会让面试官觉得你对复杂度有完整的认知。3.4 1 两数之和Map的key和value别放反两数之和是LeetCode的经典中的经典代码随想录也把它放在哈希表的最后一道。题目要求在一个数组里找两个数它们的和等于target返回两个下标。最暴力的办法是两层循环O(n^2)。用哈希表能做到一次遍历。思路是这样的遍历数组时每看到一个数nums[i]就算一下它需要搭配的数target - nums[i]在不在Map里。在的话直接返回两个下标不在的话就把当前数作为key、当前下标作为value存进Map。这里Map存的语义是“这个数出现在哪个位置”所以key一定是数值value一定是下标千万别放反。class Solution { public int[] twoSum(int[] nums, int target) { MapInteger, 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]; } }为什么一定要先查再放入这个细节非常关键。如果先put再查面对重复元素会出错。比如nums [3, 3]target 6遍历到第一个3时如果先放入map此时map里已经有(3,0)了containsKey(3)直接返回true就会返回[0,0]显然是错的。正确做法是先查再放确保不会把当前元素自己配成一对。这也是两数之和里最容易被忽略的陷阱。另外还要注意题目保证有唯一解所以找到之后可以直接返回。但代码健壮性好的话最后可以补一个return new int[0]以防万一虽然实际走不到。4. 高频踩坑与排查建议4.1 把常见问题整理成一张速查表Day05这四道题踩坑点其实很集中我整理了一个小表刷题前扫一眼能少走很多弯路问题现象可能原因排查思路两数之和返回[0,0]先put后查当前元素被自己匹配改成先查后放再put进去快乐数超时没有用Set记录历史陷入死循环每次循环前判断n是否已经在Set里字母异位词数组越界直接用字符当成索引没减a检查索引表达式确保范围在0到25349返回结果包含重复数字结果用了List没去重结果也用Set最后再转数组Integer比较用失败超出-128到127的缓存范围用equals比较或者转成intValue再判断这个表我自己的体会是大部分坑都不是因为不懂API而是因为没有把“哈希表是我自己设计的数据结构”这个思维建立起来。你设计了一个存储和查找的方案那就得对重复、碰撞、边界负责API只是最后落地的工具。4.2 一个让人懵掉的反直觉先查再放“先查再放”这个点我在跟朋友交流的时候发现很多人刷完两数之和也没注意过。他们写的代码是先把当前元素放进去再检查Map因为觉得反正迟早要放早点放也没关系。结果遇到重复元素的时候就会把自己当成答案。我建议做这道题的时候用一个反例亲手跑一遍感受特别直观。nums [3, 2, 4]target 6如果是先放再查第一个3放进mapneed是3查到3返回[0,0]错误。如果先查再放第一个3没查到need放进去第二个2没查到need放进去第三个4查到need2返回[1,2]正确。还有就是Map里存放的永远是“已经遍历过的元素”而不是“当前元素”。这个语义想明白先查再放的顺序就自然记住了。以后再遇到类似题目比如“判断数组里是否存在两个数的乘积等于target”这个顺序逻辑都是通用的。4.3 刷题时最容易翻车的Java小细节用Java刷哈希表题目有几个细节特别容易翻车我单独拎出来说。第一个是Integer的比较。HashMap的get返回的是Integer对象如果你拿它跟int比较没问题会自动拆箱如果两个Integer都用比较就要注意了JVM对-128到127之间的Integer有缓存这个范围外每次都是new新对象比较的是引用而不是值。所以凡是比较Integer的值一律用equals或者先转int。第二个是数组转Set的写法。很多人喜欢用Arrays.stream(nums).boxed().collect(Collectors.toSet())一行搞定但性能不如手写for循环。刷题时我更推荐传统for循环代码看着长一点但在时间和空间上都更可控调试也方便。第三个是不要边遍历Set边修改。在迭代HashSet的过程中如果调用remove会直接抛ConcurrentModificationException。刷题时如果需要过滤最简单的办法是先把要删的元素记下来循环结束后再统一remove或者直接用集合的removeIf。5. 把哈希表思维用到后面的题里5.1 五个信号帮你判断该上哈希学完Day05之后我最大的收获不是会做四道题而是以后看到新题能快速判断要不要用哈希表。我总结出五个信号命中任意一个都值得认真考虑哈希解法第一需要快速判断某个元素是否在集合中。这是最经典的信号。第二需要统计元素出现次数比如词频统计。第三需要建立一对一映射关系比如数值到下标。第四需要给数据去重。第五数据本身是连续的小范围整数这时候虽然本质是数组但思路仍然属于哈希思想。拿到一道题先对照这五个信号过一遍基本不会跑偏。比如后面常见的“赎金信”“同构字符串”“单词规律”几乎都是Day05这四道题换了个包装。底层逻辑从来没变过变的只是题目描述。5.2 面试时把复杂度讲到什么程度面试里聊到哈希表解法很多人只会说一句“时间复杂度O(n)空间复杂度O(n)”然后就停了。其实面试官更希望听到的是更细致的分析比如你用数组做哈希的时候空间复杂度可以说是O(1)的因为不管字符串多长数组固定26个位置这才是选数组而不是选HashMap的真正理由之一。这种细节我在面试中吃过亏。当时面一个中厂面试官问字母异位词我写了HashMap版他说你空间复杂度是多少我说O(n)。他说你能不能把空间复杂度变成O(1)我愣了好一会儿才反应过来用固定数组。那一次给我的教训很深刷题的时候如果只满足于AC面试现场真的会原形毕露。另外哈希表的“平均O(1)”和“最坏O(n)”这个区别也要主动提。因为Java的HashMap在链表转红黑树之前最坏情况下所有元素都撞到同一个桶查找就退化成链表的O(n)。虽然刷题时基本碰不到这种极端输入但能说出来说明你是懂底层的。5.3 接下来值得顺手刷掉的题Day05的题做完后我建议不要急着往下走先把同类型的题目补上几道趁热打铁形成肌肉记忆。我列一个比较顺手的清单383 赎金信和242几乎一个模子数组哈希直接套。205 同构字符串两个Map建立字符到字符的双向映射。290 单词规律本质上也是双向映射和205是一对。560 和为K的子数组前缀和加哈希这个稍难一些但能帮你理解Map的value可以存次数。15 三数之和这题哈希做起来细节很多我更推荐双指针但用来对比两种思路的复杂度演进很有价值。按这个顺序刷下来你对哈希表的理解会比只刷四道题深很多。特别是560它把“统计次数”和“查找历史记录”结合起来了算是一个很好的梯度题。我个人在实际操作中的体会是Day05这一天的价值不在于题目本身有多难而在于它逼着你第一次思考“用什么数据结构”这个问题。代码随想录前面几天的题目数据结构基本都是给定的数组也好链表也好都是现成的到了哈希表你需要自己去设计和选择这正是算法题从“会写代码”到“会设计解法”之间的一步跨越。最后再分享一个小技巧刷这四道题的时候每道题都试着用两种方式实现一种是用HashMap或HashSet另一种是用数组。对比一下代码的复杂度和提交后的耗时你对“数组在某些场景下就是比哈希表快”这句话会有特别直观的感受。这个对比做完比背十道题的收益都大。
代码随想录刷到Day05正好进入哈希表这个专题。说实话这一天的内容算是我刷题过程中的一个小转折点前几天的二分查找、双指针、滑动窗口套路都相对固定到了哈希表这里就开始考验你能不能从“暴力遍历”的思维里跳出来了。我自己刚开始刷题的时候觉得哈希表不就是会用HashSet和HashMap嘛真到面试被问到“这题为什么用数组不用set”一下子就卡住了。所以Day05的几道题看起来基础但里面的选型逻辑和边界处理才是真正拉开差距的地方。这篇文章就围绕Day05的几道经典题展开适合正在按代码随想录打卡表刷题的人也适合那些LeetCode刷了不少、但遇到哈希相关题目还是“凭感觉”选数据结构的朋友。我会把哈希表的底层逻辑、四道题完整拆解、以及我自己踩过的坑一次说清楚最后再聊聊怎么把这种思维用到后面的题目里。1. 哈希表专题为什么会在第五天出现1.1 前四天练的是“顺序思维”第五天开始换挡代码随想录的打卡表前面几天基本都是数组、链表这些东西解题思路偏线性要么是遍历要么是双指针要么是快慢指针。这些题目的核心是“怎么把数据排好序、怎么在有序结构里做查找”。而哈希表一上来就换了一种玩法——它不要求数据有序也不需要维护索引它靠的是“直接映射”。这种切换很多新人刚开始很不适应。比如给你一个字符串让你判断两个字符串是不是字母异位词前四天学到的那些技巧好像都用不太上。这时候就需要意识到一个问题当我们需要快速判断“某个元素在不在集合里”时顺序遍历是O(n)的开销而哈希表是O(1)的开销。这个思考方式的转变其实就是从“顺序思维”切到“查找思维”。我印象特别深当时我刷Day05之前自己先试着做两数之和第一反应是两层for循环提交之后虽然AC了但看到耗时很不舒服。后来才明白暴力解的问题不仅在复杂度上更在于你压根没有建立“空间换时间”的直觉。代码随想录把哈希表放在第五天其实就是想让你尽早建立这种直觉越早越好。1.2 这个专题真正要练的能力哈希表专题真正要练的不是记住HashMap怎么用而是三个能力第一个是选型能力。拿到一道题能判断出用数组、HashSet还是HashMap并且能说出理由。数组可能在O(1)时间比哈希表还快因为它不需要计算哈希值也不需要处理哈希冲突。第二个是空间复杂度的意识。哈希表本质上是空间换时间面试里经常要你回答用多少额外空间。第三个是边界控制能力。哈希表的很多坑比如重复元素、负数、空输入、Integer的装箱相等问题全都在边界里。所以Day05这几道题题目本身不难但它们是很好的训练载体。如果只满足于“把题AC了”那确实有点浪费如果能把每一道题的选型理由、复杂度、边界情况都盘一遍这一天的收获其实比后面很多难的题目都要大。2. 先搞懂哈希表的底层再谈刷题2.1 哈希函数、冲突与两种经典解决思路哈希表的底层原理并不复杂简单说它把要存储的元素通过一个哈希函数计算出一个位置然后直接存到数组的这个位置上。这样查找的时候只需要重新计算哈希值就能直接在数组的对应位置把数据取出来所以平均时间复杂度是O(1)。问题是哈希函数不可能是完美的一一映射。不同元素算出来可能落在同一个位置这种情况叫哈希冲突。解决冲突有两大流派开放定址法和链地址法。开放定址法就是位置被占了之后按某种规则继续往后找空位比如线性探测、二次探测链地址法则是每个槽位挂一个链表冲突的元素串在一起Java的HashMap在链表过长时还会把链表转成红黑树本质上也是链地址法的一种优化。我之前一直不理解为什么会有这么多细节直到有一次线下分享一个朋友用了个特别贴切的比喻哈希表就像一栋楼哈希函数决定你住哪一层但同一层可能住了很多人这时候要么换楼层开放定址法要么同一层多摆几间房链地址法。这么一想原理就通了。对刷题来说我们不需要真的实现红黑树但搞清楚冲突是怎么解决的能帮你想清楚为什么哈希表是“平均O(1)、最坏O(n)”。2.2 数组、Set、Map到底怎么选这是哈希表专题最核心的问题也是面试官最爱追着问的点。三种结构各有适用场景我的判断标准是这样的首先看key的取值范围。如果key是小范围的整数或者字符这种连续结构优先用数组。比如判断字母异位词字符一共26个你直接开一个长度为26的int数组用字符减a作为索引这天然就是一个哈希表。数组连哈希函数都不用算因为索引本身就是映射而且绝对没有冲突性能是最好的。其次看需求。如果只需要判断“元素有没有出现过”用HashSet就够了如果需要“元素到另一个信息”的映射比如元素到下标、元素到次数那就用HashMap。这个判断非常直接不要一上来就HashMap很多题用Set更轻量。最后还要看数据的密度。如果数据稀疏比如取值范围很大但实际元素很少用数组就浪费了但如果取值范围小又密集数组的空间消耗也很小。举个例子给你10000个可能出现的数但实际只有5个那你开10000长度的数组就有点傻了HashSet就合适。反之如果数字范围限定在0到100数组就一定是最优选。2.3 Java里HashMap和HashSet底层要了解哪些用Java刷题的话底层有一些细节是躲不开的。HashSet内部其实就是一个HashMap只不过它只用到keyvalue是一个固定的ObjectHashSet的add操作实际上就是在map里put(key, PRESENT)。理解这层关系你会发现两个结构的使用场景其实是一体的。另外一个高频考点是哈希值的计算。Java的String.hashCode()用的是31作为乘数为什么是31因为31是奇素数并且编译器会对31做优化31*h可以写成(h5)-h性能更好。奇素数能减少乘法溢出后信息的丢失冲突概率相对低。这个细节不一定在Day05直接考到但面试聊到HashMap的哈希函数时能说出31的原因是加分项。还有一点要注意Java 8之后HashMap在链表长度超过阈值时会树化链表长度超过8、数组容量超过64时会把链表转成红黑树。刷题时我们一般不关心这个但如果你在面试里聊HashMap的优化顺手提到这个阈值能显得你对底层是有研究的。3. 四道题逐题拆解3.1 242 有效字母异位词数组才是最省的哈希表题目很简单给定两个字符串s和t判断它们是不是字母异位词就是组成字母相同、顺序不同。这道题在有哈希表概念之前最常见的操作是先排序再比较但排序的时间复杂度是O(n log n)。用哈希表思路我们可以统计字符出现次数然后对比。代码随想录给的思路很干净因为只涉及小写字母直接申请一个长度26的int数组。先遍历第一个字符串每个字符出现对应索引加一再遍历第二个字符串出现对应索引减一最后检查数组里是不是全是0。class Solution { 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; } }这里有两个关键点值得展开。第一为什么不用HashMap因为在字符集固定且数量少的前提下数组查找是直接寻址速度比HashMap快不少。虽然都是O(1)但常数不一样刷题可能看不出差别面试一定要讲出来。第二索引为什么要减a因为char底层是数字a的ASCII码是97如果不减数组就得开到很大减了之后a对应0z对应25刚好26个位置。进阶思考如果字符串包含Unicode字符怎么办比如中文、emoji。这时候数组就不行了因为字符范围太大应该换成Mapkey是字符value是次数。这也是很多面试官喜欢追问的变体基础解法加上扩展思考才是完整的回答。3.2 349 两个数组的交集去重直接用Set第二道题是计算两个数组的交集要求结果里每个元素唯一。这题很自然地想到Set先把第一个数组的所有元素放进一个Set再遍历第二个数组如果Set里有这个元素就加入结果Set最后把结果Set转成数组。我第一遍做的时候在“用两个Set还是用一个Set”上纠结了一下。后来看到代码随想录的思路才明白一个Set做查找表一个Set做结果集就够了。查找表的Set负责去重和O(1)查找结果集的Set负责给结果去重两个各司其职。class Solution { public int[] intersection(int[] nums1, int[] nums2) { SetInteger table new HashSet(); for (int num : nums1) { table.add(num); } SetInteger resultSet new HashSet(); for (int num : nums2) { if (table.contains(num)) { resultSet.add(num); } } int[] result new int[resultSet.size()]; int index 0; for (int num : resultSet) { result[index] num; } return result; } }这题值得思考的是为什么不用数组因为题目里nums的值没有限制取值范围可能是负数也可能很大。开数组的话要么开不下要么需要做偏移转换非常别扭。Set天生就是为这种场景准备的我只关心“在不在”不关心“在哪”。复杂度上设两个数组长度分别是m和n时间复杂度是O(mn)空间复杂度是O(min(m,n))。如果你用较小的数组做查找表遍历大的数组去查空间还能更省一点。这是一个很小的优化点但面试时提出来很加分。3.3 202 快乐数题眼是判断循环快乐数这题我第一次做的时候完全没意识到这是一个哈希表题。题目说一个数不断把每一位的平方相加如果能变成1就是快乐数否则会陷入循环。看到“循环”两个字第一反应可能是快慢指针但哈希表的思路更直观用一个Set记录每一步出现过的数如果新算出来的数已经在Set里出现过说明进入了循环直接返回false。以19为例19拆成1和9平方和是82然后是68再到100最后到1所以19是快乐数。整个过程里如果某个和之前出现过了根据数学性质后面一定会无限循环但不一定回到开头那个数。核心代码非常短class Solution { public boolean isHappy(int n) { SetInteger seen new HashSet(); while (n ! 1 !seen.contains(n)) { seen.add(n); int sum 0; while (n 0) { int digit n % 10; sum digit * digit; n / 10; } n sum; } return n 1; } }这个题的题眼就是“用Set记录历史”。很多新手想当然地写一个while循环判断条件里没有Set结果死循环跑不出去。我当时看到测试用例一直超时才意识到自己根本没处理循环情况。这题的启发是题目说“不是快乐数会无限循环”其实是在提示你需要判断重复。看到“重复”和“循环”就要条件反射地想到哈希表或者快慢指针。还有一个可以聊的扩展点这题不用Set也能做用弗洛伊德判圈算法也就是快慢指针。空间复杂度可以从O(logn)降到O(1)。面试时答完哈希表解法之后补一句“还可以用快慢指针把空间降到O(1)”会让面试官觉得你对复杂度有完整的认知。3.4 1 两数之和Map的key和value别放反两数之和是LeetCode的经典中的经典代码随想录也把它放在哈希表的最后一道。题目要求在一个数组里找两个数它们的和等于target返回两个下标。最暴力的办法是两层循环O(n^2)。用哈希表能做到一次遍历。思路是这样的遍历数组时每看到一个数nums[i]就算一下它需要搭配的数target - nums[i]在不在Map里。在的话直接返回两个下标不在的话就把当前数作为key、当前下标作为value存进Map。这里Map存的语义是“这个数出现在哪个位置”所以key一定是数值value一定是下标千万别放反。class Solution { public int[] twoSum(int[] nums, int target) { MapInteger, 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]; } }为什么一定要先查再放入这个细节非常关键。如果先put再查面对重复元素会出错。比如nums [3, 3]target 6遍历到第一个3时如果先放入map此时map里已经有(3,0)了containsKey(3)直接返回true就会返回[0,0]显然是错的。正确做法是先查再放确保不会把当前元素自己配成一对。这也是两数之和里最容易被忽略的陷阱。另外还要注意题目保证有唯一解所以找到之后可以直接返回。但代码健壮性好的话最后可以补一个return new int[0]以防万一虽然实际走不到。4. 高频踩坑与排查建议4.1 把常见问题整理成一张速查表Day05这四道题踩坑点其实很集中我整理了一个小表刷题前扫一眼能少走很多弯路问题现象可能原因排查思路两数之和返回[0,0]先put后查当前元素被自己匹配改成先查后放再put进去快乐数超时没有用Set记录历史陷入死循环每次循环前判断n是否已经在Set里字母异位词数组越界直接用字符当成索引没减a检查索引表达式确保范围在0到25349返回结果包含重复数字结果用了List没去重结果也用Set最后再转数组Integer比较用失败超出-128到127的缓存范围用equals比较或者转成intValue再判断这个表我自己的体会是大部分坑都不是因为不懂API而是因为没有把“哈希表是我自己设计的数据结构”这个思维建立起来。你设计了一个存储和查找的方案那就得对重复、碰撞、边界负责API只是最后落地的工具。4.2 一个让人懵掉的反直觉先查再放“先查再放”这个点我在跟朋友交流的时候发现很多人刷完两数之和也没注意过。他们写的代码是先把当前元素放进去再检查Map因为觉得反正迟早要放早点放也没关系。结果遇到重复元素的时候就会把自己当成答案。我建议做这道题的时候用一个反例亲手跑一遍感受特别直观。nums [3, 2, 4]target 6如果是先放再查第一个3放进mapneed是3查到3返回[0,0]错误。如果先查再放第一个3没查到need放进去第二个2没查到need放进去第三个4查到need2返回[1,2]正确。还有就是Map里存放的永远是“已经遍历过的元素”而不是“当前元素”。这个语义想明白先查再放的顺序就自然记住了。以后再遇到类似题目比如“判断数组里是否存在两个数的乘积等于target”这个顺序逻辑都是通用的。4.3 刷题时最容易翻车的Java小细节用Java刷哈希表题目有几个细节特别容易翻车我单独拎出来说。第一个是Integer的比较。HashMap的get返回的是Integer对象如果你拿它跟int比较没问题会自动拆箱如果两个Integer都用比较就要注意了JVM对-128到127之间的Integer有缓存这个范围外每次都是new新对象比较的是引用而不是值。所以凡是比较Integer的值一律用equals或者先转int。第二个是数组转Set的写法。很多人喜欢用Arrays.stream(nums).boxed().collect(Collectors.toSet())一行搞定但性能不如手写for循环。刷题时我更推荐传统for循环代码看着长一点但在时间和空间上都更可控调试也方便。第三个是不要边遍历Set边修改。在迭代HashSet的过程中如果调用remove会直接抛ConcurrentModificationException。刷题时如果需要过滤最简单的办法是先把要删的元素记下来循环结束后再统一remove或者直接用集合的removeIf。5. 把哈希表思维用到后面的题里5.1 五个信号帮你判断该上哈希学完Day05之后我最大的收获不是会做四道题而是以后看到新题能快速判断要不要用哈希表。我总结出五个信号命中任意一个都值得认真考虑哈希解法第一需要快速判断某个元素是否在集合中。这是最经典的信号。第二需要统计元素出现次数比如词频统计。第三需要建立一对一映射关系比如数值到下标。第四需要给数据去重。第五数据本身是连续的小范围整数这时候虽然本质是数组但思路仍然属于哈希思想。拿到一道题先对照这五个信号过一遍基本不会跑偏。比如后面常见的“赎金信”“同构字符串”“单词规律”几乎都是Day05这四道题换了个包装。底层逻辑从来没变过变的只是题目描述。5.2 面试时把复杂度讲到什么程度面试里聊到哈希表解法很多人只会说一句“时间复杂度O(n)空间复杂度O(n)”然后就停了。其实面试官更希望听到的是更细致的分析比如你用数组做哈希的时候空间复杂度可以说是O(1)的因为不管字符串多长数组固定26个位置这才是选数组而不是选HashMap的真正理由之一。这种细节我在面试中吃过亏。当时面一个中厂面试官问字母异位词我写了HashMap版他说你空间复杂度是多少我说O(n)。他说你能不能把空间复杂度变成O(1)我愣了好一会儿才反应过来用固定数组。那一次给我的教训很深刷题的时候如果只满足于AC面试现场真的会原形毕露。另外哈希表的“平均O(1)”和“最坏O(n)”这个区别也要主动提。因为Java的HashMap在链表转红黑树之前最坏情况下所有元素都撞到同一个桶查找就退化成链表的O(n)。虽然刷题时基本碰不到这种极端输入但能说出来说明你是懂底层的。5.3 接下来值得顺手刷掉的题Day05的题做完后我建议不要急着往下走先把同类型的题目补上几道趁热打铁形成肌肉记忆。我列一个比较顺手的清单383 赎金信和242几乎一个模子数组哈希直接套。205 同构字符串两个Map建立字符到字符的双向映射。290 单词规律本质上也是双向映射和205是一对。560 和为K的子数组前缀和加哈希这个稍难一些但能帮你理解Map的value可以存次数。15 三数之和这题哈希做起来细节很多我更推荐双指针但用来对比两种思路的复杂度演进很有价值。按这个顺序刷下来你对哈希表的理解会比只刷四道题深很多。特别是560它把“统计次数”和“查找历史记录”结合起来了算是一个很好的梯度题。我个人在实际操作中的体会是Day05这一天的价值不在于题目本身有多难而在于它逼着你第一次思考“用什么数据结构”这个问题。代码随想录前面几天的题目数据结构基本都是给定的数组也好链表也好都是现成的到了哈希表你需要自己去设计和选择这正是算法题从“会写代码”到“会设计解法”之间的一步跨越。最后再分享一个小技巧刷这四道题的时候每道题都试着用两种方式实现一种是用HashMap或HashSet另一种是用数组。对比一下代码的复杂度和提交后的耗时你对“数组在某些场景下就是比哈希表快”这句话会有特别直观的感受。这个对比做完比背十道题的收益都大。
