哈希理解核心思想哈希的本质用空间换时间。具体体现如下正常查找数组查找O(n)哈希查找HashMap查找O(1)流程key → hash函数 → hash值 → 数组下标例keyabchash(abc)123456index123456%tableSizeHot100 哈希题型分类类型思维代表题查找是否存在一边遍历一边查两数之和统计次数计数有效字母异位词分组key相同归类字母异位词分组前缀信息记录历史状态和为K的子数组1️⃣ 两数之和 → 查找型 Hash2️⃣ 字母异位词分组 → 分组型 Hash3️⃣ 最长连续序列 → 集合型 Hash去重 O(1) 查找一、两数之和Hash查找模型思考Level 1方向性提示先不要急着想 两个数怎么组合。换个角度思考当你遍历数组时如果当前数字是 x其实你真正想找的是 另一个特定的数字。问自己一个问题如果当前数字是 x那另一个数字应该是多少把问题从找两个数变成找一个特定的数是否存在想一想有没有一种数据结构可以让你“快速判断一个数是否已经出现过”Level 2关键突破点当你遍历数组到某个数字 x 时你真正想找的是target - x例如nums [2,7,11,15]target 9当你看到x 7你其实在找9 - 7 2所以关键问题变成在之前遍历过的数字里 有没有 2 也就是说你需要在遍历过程中 记录之前出现过的数字并且能 快速判断某个数字是否已经出现过。思考两个问题1️⃣ 用什么数据结构可以快速判断一个数是否存在2️⃣ 如果找到了这个数你是否还需要知道它在数组里的位置题解publicint[]twoSum(int[]nums,inttarget){MapInteger,IntegermapnewHashMap();for(inti0;inums.length;i){intneedtarget-nums[i];if(map.containsKey(need)){returnnewint[]{map.get(need),i};}map.put(nums[i],i);}returnnewint[0];}核心点在于我们通过遍历数组得到target - nums[i]在map中寻找是否存在如果存在则得到答案。于是流程如下遍历数组↓计算 need target - nums[i]↓map 是否存在 need↓存在 → 返回不存在 → 存入 map二、字母异位词分组Hash分组模型Level 1方向性提示算法思想先观察题目的核心关系eat tea ate这些字符串为什么会被分到同一组因为它们有一个特点字符完全相同 只是顺序不同所以你需要思考一个问题有没有办法把 “字符相同但顺序不同” 的字符串转换成同一个特征表示如果可以做到多个字符串 → 同一个特征那这个特征就可以作为 HashMap 的 key 来进行分组。Level 2关键突破点现在思考一个非常关键的问题如何让eat tea ate变成同一个 key想象一种操作如果对字符串做某种 标准化处理让所有异位词都得到 相同的结果。例如eat → ? tea → ? ate → ?如果这个处理后的结果完全一样? ?那么你就可以用这个结果作为key然后把原字符串放到同一个 list 里。所以你的数据结构很可能是key - List题解publicListListStringgroupAnagrams(String[]strs){MapString,ListStringmapnewHashMap();for(Stringstr:strs){char[]charsstr.toCharArray();Arrays.sort(chars);StringkeynewString(chars);map.putIfAbsent(key,newArrayList());map.get(key).add(str);}returnnewArrayList(map.values());}核心点在于我们先将字符串数组进行遍历得到字符串排序这排序后的结果就相当于key将key放入到map中最终进行打印。流程图遍历字符串数组↓字符串排序↓得到key↓放入map三、最长连续序列题解publicintlongestConsecutive(int[]nums){SetIntegersetnewHashSet();for(intnum:nums){set.add(num);}intlongest0;for(intnum:set){if(!set.contains(num-1)){intcurrentnum;intlength1;while(set.contains(current1)){current;length;}longestMath.max(longest,length);}}returnlongest;}解题流程数组 → HashSet↓遍历每个 num↓如果 num-1 不存在↓开始向右扩展num1num2num3