摘要本文解析力扣LeetCodeHot 100 中三道经典的哈希表应用题目两数之和、字母异位词分组和最长连续序列。1. 两数之和 (Two Sum)1.1 问题描述给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值target的那两个整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案并且你不能重复使用相同的元素。1.2 核心思路暴力解法是双层循环遍历所有组合时间复杂度为 O(n²)。更优的方法是使用哈希表来存储遍历过的数字及其索引。对于当前数字nums[i]我们计算其补数temp target - nums[i]然后检查补数是否已存在于哈希表中。如果存在则找到答案如果不存在则将当前数字及其索引存入哈希表供后续查找。1.3 代码实现与讲解// 两数之和 public class Solution { public int[] TwoSum(int[] nums, int target) { // 创建一个字典用来存储数字-索引的对应关系 Dictionaryint, int dic new Dictionaryint, int(); for (int i 0; i nums.Length; i) { // 计算当前数字需要的另一半是多少 int temp target - nums[i]; // 检查字典里有没有这个另一半 if (dic.ContainsKey(temp)) { // 找到了返回另一半的索引和当前索引 return [dic[temp], i]; } // 如果当前数字还没存到字典里就存进去 if (!dic.ContainsKey(nums[i])) { dic[nums[i]] i; } } return [0, 0]; } }为什么这样高效因为字典的查找速度非常快平均O(1)我们只需要遍历一次数组就能找到答案。这比暴力解法两层循环快多了。1.4 复杂度分析时间复杂度O(n)。我们只遍历了一次数组每次哈希表的查找和插入操作平均时间复杂度为 O(1)。空间复杂度O(n)。最坏情况下我们需要将 n 个元素全部存入哈希表。2. 字母异位词分组 (Group Anagrams)2.1 问题描述给你一个字符串数组strs请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。2.2 核心思路字母异位词的关键特征是排序后的字符串是相同的。因此我们可以将每个字符串排序后的结果作为哈希表的键原始字符串作为值列表中的一员。算法步骤遍历字符串数组中的每个字符串。将当前字符串转换为字符数组并排序得到排序后的字符串作为键。检查哈希表中是否存在该键。如果不存在则创建一个新的空列表作为值。将原始字符串添加到该键对应的列表中。遍历完成后返回哈希表中所有值列表的集合。2.3 代码实现与讲解// 字母异位词分组 public class Solution { public ListIListstring GroupAnagrams(string[] strs) { // 创建一个字典键是排序后的字符串值是原始字符串列表 Dictionarystring, Liststring dic new Dictionarystring, Liststring(); foreach (string str in strs) { // 把当前字符串排序得到标准格式 string newStr ToArray(str); // 如果字典里还没有这个标准格式就创建一个新列表 if (!dic.ContainsKey(newStr)) { dic[newStr] new Liststring(); } // 把原始字符串添加到对应的列表中 dic[newStr].Add(str); } // 返回字典里所有的值就是分组结果 return new ListIListstring(dic.Values); } // 辅助方法把字符串排序后返回 public string ToArray(string str) { char[] s str.ToCharArray(); // 把字符串变成字符数组 Array.Sort(s); // 对字符数组排序 return new string(s); // 把排序后的字符数组变回字符串 } }2.4 复杂度分析时间复杂度O(n * k log k)。其中 n 是字符串数组的长度k 是单个字符串的最大长度。我们需要对每个字符串进行排序O(k log k)。空间复杂度O(n * k)。哈希表需要存储所有字符串原始或排序后的形式。3. 最长连续序列 (Longest Consecutive Sequence)3.1 问题描述给定一个未排序的整数数组nums找出数字连续的最长序列不要求序列元素在原数组中连续的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。3.2 核心思路暴力解法是排序后遍历但排序需要 O(n log n) 时间。要达到 O(n) 时间复杂度核心是利用哈希集合HashSetint实现 O(1) 时间复杂度的查找。算法步骤将所有数字放入一个哈希集合中以便快速判断一个数是否存在。遍历数组中的每个数字num。对于每个数字检查num - 1是否存在于集合中。如果不存在说明num可能是一个连续序列的起点。如果num是起点则从num开始不断检查num 1,num 2... 是否在集合中并计算当前连续序列的长度。更新全局最大长度。此方法确保每个连续序列只被遍历一次因此总时间复杂度为 O(n)。3.3 代码实现与讲解// 最长连续序列 public class Solution { public int LongestConsecutive(int[] nums) { // 处理空数组的情况 if (nums null) return 0; // 把所有数字放进一个集合里方便快速查找 HashSetint set new HashSetint(nums); int maxL 1; // 记录最长连续序列的长度 foreach (int n in nums) { // 关键思路只从连续序列的起点开始数 // 如果 n-1 不在集合里说明 n 可能是一个起点 if (!set.Contains(n - 1)) { int nowN n; // 当前数字 int nowL 1; // 当前连续序列长度 // 从起点开始往后数连续的数字 while (set.Contains(nowN 1)) { nowL; nowN; } // 更新最大长度 maxL Math.Max(maxL, nowL); } } return maxL; } }3.4 复杂度分析时间复杂度O(n)。虽然代码有嵌套循环但每个数字最多被访问两次一次在外层循环判断起点一次在内层循环扩展序列因此总体是线性复杂度。空间复杂度O(n)。哈希集合存储了所有 n 个数字。4. 总结哈希表Dictionary/HashSet是解决这类查找、分组和去重问题的利器它能将查找时间降至 O(1)从而帮助我们将算法优化到 O(n) 级别。两数之和利用哈希表存储“值-索引”映射将查找补数的时间降至 O(1)。字母异位词分组利用排序后的字符串作为哈希键将异位词归到同一组。最长连续序列利用哈希集合实现 O(1) 存在性检查并巧妙地通过判断“前驱数是否存在”来避免重复遍历同一序列。