LeetCode哈希表应用精讲：从字母异位词到两数之和

1. Leetcode哈希表专题精讲从字母异位词到两数之和作为一名刷过800题的Leetcode老手我发现在数据结构中哈希表是最高频出现的解题工具之一。今天我们就来深度剖析哈希表在Leetcode中的经典应用场景通过4道代表性题目242.有效的字母异位词、349.两个数组的交集、202.快乐数、1.两数之和掌握其核心用法。哈希表Hash Table本质上是通过键值对存储数据的结构平均情况下能以O(1)时间复杂度完成数据查找。在算法题中当我们需要快速判断元素是否存在、统计元素出现次数或建立映射关系时哈希表往往是首选方案。下面我将结合具体题目展示如何用Python和Java两种语言实现高效解法并分享我在刷题过程中总结的优化技巧。2. 242.有效的字母异位词哈希计数法的经典应用2.1 问题重述与解法分析给定两个字符串s和t判断t是否是s的字母异位词即字母组成相同但排列顺序不同。例如输入s anagram, t nagaram → 输出true输入s rat, t car → 输出false核心思路统计每个字母出现的次数是否一致。哈希表天然适合这种频率统计场景。2.2 Python实现与优化def isAnagram(s: str, t: str) - bool: if len(s) ! len(t): return False count [0] * 26 # 使用数组模拟哈希表 for char in s: count[ord(char) - ord(a)] 1 for char in t: count[ord(char) - ord(a)] - 1 if count[ord(char) - ord(a)] 0: return False return True技巧当键范围明确且有限如26个小写字母时用数组代替哈希表可以提升性能。ord(char) - ord(a)将字母映射到0-25的索引。2.3 Java实现对比public boolean isAnagram(String s, String t) { if (s.length() ! t.length()) return false; int[] counts new int[26]; for (char c : s.toCharArray()) { counts[c - a]; } for (char c : t.toCharArray()) { if (--counts[c - a] 0) { return false; } } return true; }2.4 复杂度分析与边界条件时间复杂度O(n)n为字符串长度空间复杂度O(1)固定大小的计数数组边界处理长度不等直接返回false注意Unicode字符的情况此时需用真正的哈希表3. 349.两个数组的交集集合操作的实践3.1 问题描述与解法选择给定两个数组nums1和nums2返回它们的交集结果唯一且无序。例如输入nums1 [1,2,2,1], nums2 [2,2] → 输出[2]解题思路利用集合Set去重特性Python中直接使用内置集合操作。3.2 Python优雅解法def intersection(nums1: List[int], nums2: List[int]) - List[int]: return list(set(nums1) set(nums2))3.3 Java实现细节public int[] intersection(int[] nums1, int[] nums2) { SetInteger set1 new HashSet(); SetInteger resultSet new HashSet(); for (int num : nums1) set1.add(num); for (int num : nums2) { if (set1.contains(num)) { resultSet.add(num); } } return resultSet.stream().mapToInt(i-i).toArray(); }3.4 进阶讨论如果数组已排序可以使用双指针法空间复杂度O(1)当内存有限时可以优先处理较小的数组构建哈希表实际工程中要考虑元素哈希冲突的处理4. 202.快乐数哈希检测循环4.1 问题理解判断一个数是否为快乐数将该数替换为各位数字平方和重复这个过程直到变为1快乐数或进入不包含1的循环。例如19 → 1² 9² 82 → 8² 2² 68 → ... → 1 → True2 → 4 → 16 → 37 → ... → 进入循环 → False4.2 哈希解法实现def isHappy(n: int) - bool: seen set() while n ! 1: if n in seen: return False seen.add(n) n sum(int(d)**2 for d in str(n)) return True4.3 数学优化思路所有不快乐数最终都会进入4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4的循环因此可以简化为只检查n是否为4def isHappy(n: int) - bool: while n ! 1 and n ! 4: n sum(int(d)**2 for d in str(n)) return n 14.4 复杂度讨论时间复杂度O(logn)数字位数处理空间复杂度O(logn)哈希表存储中间结果5. 1.两数之和哈希表的招牌应用5.1 题目回顾给定数组nums和目标值target找出和为target的两个数的索引。例如输入nums [2,7,11,15], target 9 → 输出[0,1]5.2 最优解法实现def twoSum(nums: List[int], target: int) - List[int]: num_map {} for i, num in enumerate(nums): complement target - num if complement in num_map: return [num_map[complement], i] num_map[num] i return []5.3 Java版本public int[] twoSum(int[] nums, int target) { MapInteger, Integer map new HashMap(); for (int i 0; i nums.length; i) { int complement target - nums[i]; if (map.containsKey(complement)) { return new int[] {map.get(complement), i}; } map.put(nums[i], i); } throw new IllegalArgumentException(No solution); }5.4 常见错误与陷阱先构建完整哈希表再查找可能错过相同元素的解如[3,3], target6忽略输入为空或无解的情况返回元素值而非索引题目要求返回索引6. 哈希表专题总结与进阶技巧6.1 四道题目的共性分析快速查找都利用了哈希表O(1)查询的特性空间换时间通过额外空间降低时间复杂度键设计根据问题特点设计合适的键字母、数值、中间结果等6.2 高频面试考点哈希冲突处理开放寻址法 vs 链地址法哈希函数设计原则不同语言中哈希表的实现差异Python字典、Java HashMap等6.3 性能优化实践当键范围有限时优先使用数组代替哈希表对于对象作为键的情况确保正确实现hashCode()和equals()注意哈希表扩容带来的性能影响初始化时预估大小6.4 扩展练习题推荐205.同构字符串290.单词规律454.四数相加II128.最长连续序列在实际刷题过程中我发现很多同学容易陷入记住解法的误区。真正掌握哈希表的关键在于理解其适用场景——当你需要快速判断元素是否存在、需要建立映射关系或统计频率时就该考虑哈希表了。建议从这四道基础题出发逐步挑战更复杂的哈希表应用比如与滑动窗口结合的题目3.无重复字符的最长子串或者多哈希表配合使用的场景。