第1类题型哈希表为什么哈希表题看起来简单你却最容易写错很多同学第一次刷哈希表题时会觉得这类题不难因为经典题像两数之和、存在重复元素看上去都不复杂。但真到了面试现场哈希表反而是最容易暴露基本功的一类题原因通常有这几种你知道这题和“查找”有关但第一反应还是双重循环。你隐约觉得要用哈希结构却分不清该用Map还是Set。你会写HashMap但“先查再放”还是“先放再查”总是容易写反。你能把代码写出来却说不清为什么它能把复杂度从O(n^2)压到O(n)。如果你现在正处在“会做部分 Easy但题面一变就没把握面试一追问就容易乱”的阶段这一类题最值得先练。读完这篇你至少要把 3 件事练熟看到题先想到哈希、能把模板写稳、能在面试里把思路讲清楚。文章目录第1类题型哈希表为什么哈希表题看起来简单你却最容易写错1. 核心知识点动画辅助理解先查 complement再写入 map2. 这类题在面试里考什么3. 高频题清单4. 这类题最容易犯的 3 个错误5. 代表题精讲 1题目思路Java 代码复杂度如果这是面试现场你可以这样说手推一遍最容易记住的状态变化6. 代表题精讲 2题目思路Java 代码复杂度如果这是面试现场你可以这样说为什么这里用 Set 就够了7. 其余题模板与关键片段[217. 存在重复元素](https://leetcode.cn/problems/contains-duplicate/)[242. 有效的字母异位词](https://leetcode.cn/problems/valid-anagram/)8. 边界、易混点与替代方案Map 和 Set 怎么选哈希和排序怎么选哈希和计数数组怎么选哪些情况要格外小心9. 你学完后怎么验证自己真的会了10. 错题本记录方式11. 适用范围与边界12. 面试前 3 分钟速记13. 结尾把“会做题”变成“会识别、会写、会讲”1. 核心知识点哈希表最适合解决这几类问题查某个值是否存在。统计某个元素出现次数。建立“值到位置”或“值到次数”的映射。去重。把原本需要两层循环的查找压成一层循环。实习面试里你可以先这样判断如果题目里出现“是否存在”“两数配对”“出现次数”“去重”“映射关系”优先想哈希表。Java 里最常用的是两个结构HashMapK, V需要存键值对时用。HashSetE只关心某个元素是否出现过时用。最常见的写法有这几类MapInteger,IntegermapnewHashMap();map.put(nums[i],i);map.get(target);map.getOrDefault(x,0);SetIntegersetnewHashSet();set.add(x);set.contains(x);边界上最容易错的是两件事先判断还是先插入。值重复时旧下标是否会被覆盖。动画辅助理解先查 complement再写入 map哈希表题最适合用1. 两数之和来建立第一印象。你可以先打开本地动画页哈希表两数之和分步动画这个动画只看一件事遍历到当前数时先计算它缺的另一个数也就是complement target - nums[i]再去map里查这个 complement 是否已经出现过。以nums [2, 7, 11, 15]、target 9为例当前值需要的 complement查询 map下一步27查不到7把2 - 0写入 map72查到2 - 0返回[0, 1]这一步能解释为什么代码必须“先查再放”。如果你先把当前的7放进 map再去查 complement就会混淆“之前出现过的数”和“当前正在处理的数”。在面试里哈希表题经常不是难在 API而是难在这个状态更新顺序。2. 这类题在面试里考什么哈希表题的面试考察很基础但非常能看出习惯是否成熟。你能不能把暴力查找压成线性时间。你是否熟悉 Java 的Map/Set写法。你能不能在一次遍历里同时维护状态和答案。你是否会处理重复值、缺失值、默认值这些细节。面试官想看到的不是你会背HashMap定义而是你能快速说出为什么不用双重循环。为什么这里用Map而不是Set。为什么这里应该先查再放或者先放再查。3. 高频题清单题目来源难度高频属性1. 两数之和LeetCode 热题 100Easy面试高频217. 存在重复元素面试经典 150Easy面试高频242. 有效的字母异位词面试经典 150Easy基础高频128. 最长连续序列LeetCode 热题 100Medium真实面经高频4. 这类题最容易犯的 3 个错误题目本质是查找和配对结果还在写双重循环。该用Set的地方用了Map把简单题写复杂。Map更新顺序写反导致同一个元素被重复使用或下标覆盖。5. 代表题精讲 1题目1. 两数之和思路暴力做法是双重循环枚举每一对数看它们的和是不是target复杂度是O(n^2)。更好的办法是边遍历边查找。假设当前数是nums[i]那我只需要看前面有没有一个数等于target - nums[i]。这个“前面有没有”非常适合用哈希表维护。因此做法是遍历数组。先查哈希表中是否存在target - nums[i]。如果存在直接返回答案。如果不存在把当前值和当前下标放进哈希表。这里“先查再放”非常关键因为题目不允许同一个元素使用两次。Java 代码importjava.util.HashMap;importjava.util.Map;classSolution{publicint[]twoSum(int[]nums,inttarget){MapInteger,IntegerindexMapnewHashMap();for(inti0;inums.length;i){intneedtarget-nums[i];if(indexMap.containsKey(need)){returnnewint[]{indexMap.get(need),i};}indexMap.put(nums[i],i);}returnnewint[0];}}复杂度时间复杂度O(n)空间复杂度O(n)如果这是面试现场你可以这样说这题我会先把它归类为哈希查找题。暴力做法是双重循环时间复杂度O(n^2)。更好的做法是一边遍历一边用HashMap记录已经出现过的数字及其下标。对于当前元素nums[i]只需要看target - nums[i]是否已经出现过。如果出现过就能直接得到答案这样整体时间复杂度降到O(n)。手推一遍最容易记住的状态变化以nums [2, 7, 11, 15]、target 9为例当前下标i当前值nums[i]需要找的值target - nums[i]哈希表查询前内容结果027{}找不到放入2 - 0172{20}找到返回0, 1这个过程最值得记住的不是答案本身而是顺序先查补数再放当前元素。只要你把顺序写反就有机会把同一个元素错误复用两次。6. 代表题精讲 2题目128. 最长连续序列思路这题最容易误入排序思路。排序后当然能做但时间复杂度是O(n log n)。题目真正想考的是你能不能用哈希表把它压到O(n)。关键观察是如果一个数x的前一个数x - 1不存在那么x就可能是一段连续序列的起点。只有在起点处才继续向后扩展统计长度。做法先把所有数放进HashSet。遍历每个数x。如果x - 1存在说明它不是起点跳过。如果x - 1不存在就从x开始不断检查x 1, x 2...。统计最长长度。这样每个数最多被作为扩展的一部分检查一次总体还是线性复杂度。Java 代码importjava.util.HashSet;importjava.util.Set;classSolution{publicintlongestConsecutive(int[]nums){SetIntegersetnewHashSet();for(intnum:nums){set.add(num);}intbest0;for(intnum:set){if(set.contains(num-1)){continue;}intcurrentnum;intlength1;while(set.contains(current1)){current;length;}bestMath.max(best,length);}returnbest;}}复杂度时间复杂度O(n)空间复杂度O(n)如果这是面试现场你可以这样说这题虽然也能排序做但排序会把复杂度带到O(n log n)。如果想做到线性时间关键是把所有元素放进HashSet然后只从“可能的起点”开始往后扩展。判断起点的方法是看num - 1是否不存在。这样可以避免重复扫描同一段连续区间。为什么这里用Set就够了这题不需要记录下标也不需要记录次数真正需要的是两件事某个数是否存在。某个数是不是一段连续区间的起点。这两件事都只和“存在性”有关所以HashSet已经足够。很多同学会下意识写成MapInteger, Integer但那只会让代码更重并没有提供额外价值。7. 其余题模板与关键片段217. 存在重复元素核心就是去重SetIntegerseennewHashSet();for(intnum:nums){if(!seen.add(num)){returntrue;}}returnfalse;242. 有效的字母异位词如果只包含小写字母直接用计数数组int[]countnewint[26];for(charc:s.toCharArray())count[c-a];for(charc:t.toCharArray())count[c-a]--;for(intx:count){if(x!0)returnfalse;}returntrue;这题的重点不是哈希一定比数组好而是你要知道在字符范围固定时数组比MapCharacter, Integer更直接。8. 边界、易混点与替代方案Map和Set怎么选只关心元素是否出现过优先Set还要记录下标、次数、映射关系优先Map如果你发现自己在代码里存了一个值却从头到尾没有用到这个值对应的附加信息通常就说明结构选重了。哈希和排序怎么选很多题都能“排序后再做”但排序会改变复杂度也可能打乱原始下标信息。像两数之和这类要保留下标的题哈希往往更直接像最长连续序列这种题排序可做但不是题目真正想考的最优思路。哈希和计数数组怎么选如果值域或字符集固定计数数组常常比哈希更轻比如有效的字母异位词。如果值域不固定、需要通用映射能力哈希就更稳。哪些情况要格外小心题目不允许同一个元素用两次时重点检查“先查后放”。题目有重复值时重点检查旧值被覆盖后是否影响答案。题目只问存在性时别把简单题写成维护复杂映射的大题。9. 你学完后怎么验证自己真的会了不要只看完文章就算结束。更有效的做法是用下面 3 组自测来判断你是否真的掌握10 分钟内独立写出两数之和并且不用回忆题解文字只靠“先查再放”的识别信号完成。看见最长连续序列时能主动说出为什么不是必须排序为什么只从起点开始扩展。看到存在重复元素、有效的字母异位词这类题时能快速判断该用Set、Map还是计数数组。如果你在自测时出现下面任意一种情况就说明还没有真正掌握能看懂代码但自己从空白开始写不出来。写得出来但说不清为什么复杂度是O(n)。知道要用哈希但结构一会儿用Map一会儿用Set没有判断标准。比较稳妥的过关标准是你能在 15 分钟内做出一道基础哈希题并且在 1 分钟内口述题型判断、核心思路和复杂度。10. 错题本记录方式哈希表题建议重点记录这几类卡点我到底为什么没想到用哈希而是写了暴力。我是否判断错了应该用Map还是Set。我是“先查后放”写错还是默认值更新写错。这题的识别信号是什么比如“配对”“频次”“去重”“是否存在”。11. 适用范围与边界本文默认你已经会 Java 数组遍历、条件判断和基础集合写法。本文重点服务于 Java 实习面试、LeetCode 高频 Easy / Medium 和常见笔试基础题。本文不覆盖哈希冲突底层实现、并发哈希容器或竞赛向复杂技巧。如果你当前连HashMap/HashSet的基本 API 都不熟建议先补 Java 集合基础再回来刷这类题效果会更好。12. 面试前 3 分钟速记看到“配对、是否存在、频次、去重”优先想哈希表。只关心是否出现过用HashSet。还要记下标或次数用HashMap。两数之和记住“先查再放”。最长连续序列记住“只从起点开始扩展”。Java 常用写法containsKey、getOrDefault、add返回值。13. 结尾把“会做题”变成“会识别、会写、会讲”哈希表之所以适合作为第一类题型不是因为它最简单而是因为它最适合帮你建立题型意识。你从这类题开始练最重要的收获不是记住某道题的答案而是养成几个稳定动作看到题先判断是不是“存在性、配对、频次、去重”问题。写代码时先想清楚Map和Set的职责区别。做完题后能用一句话解释为什么哈希把暴力查找压成了线性复杂度。如果这几个动作稳定下来后面的双指针、滑动窗口、图论和动态规划你都会更容易进入状态。感谢阅读记得点赞、关注、收藏欢迎各位评论区交流下一篇继续看第 2 类高频题型双指针。
