【算法专题】哈希表：从“两数之和”到“最长连续序列”的深度解析

寻星探路的个人简介：

在 LeetCode 刷题过程中，哈希表（Hash Table）是出现频率最高、应用最广的数据结构之一。它的核心价值在于：**将原本需要 甚至 的查找时间复杂度降低到 **。

本文将通过三道经典题目，带你由浅入深掌握哈希表的应用精髓。

一、 两数之和 (Two Sum)

1. 题目描述

给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

2. 解题思路：空间换时间

最朴素的方法是暴力双循环，时间复杂度为 。
利用哈希表，我们可以在遍历数组的同时，记录下每一个数字及其下标。对于当前的数字nums[i]，我们只需要去哈希表中查找是否存在target - nums[i]。

3. 代码实现 (Java)

classSolution{publicint[]twoSum(int[]nums,inttarget){// Key: 数值, Value: 下标Map<Integer,Integer>map=newHashMap<>();for(inti=0;i<nums.length;i++){// 先检查补数是否存在if(map.containsKey(target-nums[i])){returnnewint[]{map.get(target-nums[i]),i};}// 再将当前元素存入 mapmap.put(nums[i],i);}returnnewint[0];}}

二、 字母异位词分组 (Group Anagrams)

1. 题目描述

给你一个字符串数组，请你将字母异位词组合在一起。字母异位词是由重新排列源单词的字母得到的一个新单词（例如 “eat” 和 “tea”）。

2. 解题思路：寻找“公共特征”作为 Key

字母异位词的特点是：虽然字母顺序不同，但排序后的字符串是完全相同的。
因此，我们可以将“排序后的字符串”作为哈希表的Key，将“原始字符串列表”作为Value。

3. 代码实现 (Java)

classSolution{publicList<List<String>>groupAnagrams(String[]strs){Map<String,List<String>>map=newHashMap<>();for(Stringstr:strs){// 将字符串转为字符数组并排序char[]array=str.toCharArray();Arrays.sort(array);Stringkey=newString(array);// 获取对应的分组列表，若不存在则创建List<String>list=map.getOrDefault(key,newArrayList<String>());list.add(str);map.put(key,list);}returnnewArrayList<List<String>>(map.values());}}

三、 最长连续序列 (Longest Consecutive Sequence)

1. 题目描述

给定一个未排序的整数数组nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。要求时间复杂度为 。

由于要求 ，我们不能进行全局排序。

1. 使用HashSet存储所有数字，实现 查询。
2. 遍历集合中的每个数num。
3. 关键点：如果num - 1存在于集合中，说明num不是连续序列的起点，直接跳过。只有当num是起点时（即num - 1不存在），才开始循环匹配num + 1, num + 2...。

3. 代码实现 (Java)

classSolution{publicintlongestConsecutive(int[]nums){Set<Integer>num_set=newHashSet<Integer>();for(intnum:nums){num_set.add(num);}intlongestStreak=0;for(intnum:num_set){// 只有当 num 是序列起点时才开始计算if(!num_set.contains(num-1)){intcurrentNum=num;intcurrentStreak=1;while(num_set.contains(currentNum+1)){currentNum+=1;currentStreak+=1;}longestStreak=Math.max(longestStreak,currentStreak);}}returnlongestStreak;}}

💡 总结：哈希表类题目的思考通用公式

面对哈希表题目，可以按照以下三个步骤进行思考：

1. 明确“我们要找什么？”

• 查找是否存在？—— 使用HashSet。
• 查找对应的关联信息（下标、次数、分组）？—— 使用HashMap。

2. 寻找“不变的 Key”

这是哈希表题目的灵魂。你需要找到一个特征，让所有符合条件的元素都能映射到同一个 Key 上：

• 两数之和：Key 是数字本身，通过target - x寻找关联。
• 字母异位词：Key 是排序后的字符串（或字符计数的数组）。
• 分组/去重：Key 是能够代表该类别唯一特征的值。

3. 优化“遍历的冗余”

在“最长连续序列”中，我们通过!num_set.contains(num - 1)过滤掉了大量的重复计算。在处理哈希表时，思考**“我是否在重复处理同一个序列？”或“我能否在一次遍历中同时完成存入和查找？”**（如两数之和），是提升算法效率的关键。

感谢阅读！如果觉得有帮助，欢迎点赞、收藏、关注！