哈希表算法实战：从基础到LeetCode经典题解

1. 哈希表算法复健从基础到实战今天咱们聊聊哈希表这个数据结构在算法题中的应用。作为算法工程师日常必备技能哈希表能高效解决很多看似复杂的问题。我挑选了LeetCode上4道经典题目242、349、202、1通过它们带你彻底掌握哈希表的应用场景和实现技巧。哈希表本质上是通过哈希函数将键映射到存储位置的数据结构平均情况下能实现O(1)时间复杂度的查找操作。在实际算法题中它特别适合处理需要快速判断元素是否存在、统计元素出现次数这类需求。下面我会结合具体题目展示如何用哈希表优雅解题。2. LC 242. 有效的字母异位词2.1 问题重述给定两个字符串s和t判断t是否是s的字母异位词即字母相同但排列不同。例如输入: s anagram, t nagaram 输出: true2.2 哈希表解法最直接的思路是用哈希表统计每个字母出现的次数def isAnagram(s: str, t: str) - bool: if len(s) ! len(t): return False count {} for char in s: count[char] count.get(char, 0) 1 for char in t: if char not in count or count[char] 0: return False count[char] - 1 return True2.3 优化技巧对于仅包含小写字母的情况可以用固定大小的数组代替哈希表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注意使用数组时要注意字符范围如果可能包含Unicode字符还是应该用哈希表3. LC 349. 两个数组的交集3.1 问题描述给定两个数组nums1和nums2返回它们的交集。输出结果中的每个元素必须是唯一的。示例输入nums1 [1,2,2,1], nums2 [2,2] 输出[2]3.2 哈希集合解法使用集合可以自动去重def intersection(nums1, nums2): set1 set(nums1) set2 set(nums2) return list(set1 set2)3.3 进阶思考如果内存有限可以只将一个数组转为集合def intersection(nums1, nums2): set1 set(nums1) res [] for num in nums2: if num in set1: res.append(num) set1.remove(num) # 避免重复添加 return res4. LC 202. 快乐数4.1 问题定义快乐数定义为对于一个正整数每次将该数替换为它每个位置上的数字的平方和重复这个过程直到结果为1此时就是快乐数或者无限循环但始终变不到1。示例输入19 输出true 解释 1² 9² 82 8² 2² 68 6² 8² 100 1² 0² 0² 14.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 数学优化实际上可以不用哈希表用快慢指针法检测循环def isHappy(n: int) - bool: def get_next(number): return sum(int(d)**2 for d in str(number)) slow n fast get_next(n) while fast ! 1 and slow ! fast: slow get_next(slow) fast get_next(get_next(fast)) return fast 15. LC 1. 两数之和5.1 经典问题给定一个整数数组nums和一个整数目标值target找出和为目标值的那两个整数并返回它们的数组下标。示例输入nums [2,7,11,15], target 9 输出[0,1]5.2 哈希表解法暴力解法是O(n²)用哈希表可以优化到O(n)def twoSum(nums, target): 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 边界情况处理实际编码时要注意数组中可能有重复元素确保不重复使用同一个元素确保有解题目保证有解时可以忽略6. 哈希表实战技巧总结6.1 选择合适的数据结构Python中常用dict和set对于固定范围的小整数可以用数组代替Java中HashMap和HashSetC中unordered_map和unordered_set6.2 常见应用场景快速查找元素是否存在统计元素出现频率记录元素位置或状态检测循环或重复6.3 性能优化要点预估数据规模初始化合适容量考虑哈希冲突的影响在时间和空间之间权衡利用语言特性如Python的集合操作7. 高频面试问题解析7.1 哈希表底层实现原理大多数语言中的哈希表使用数组链表/红黑树实现。当哈希冲突时会在同一个桶中使用链表存储当链表过长时可能转为红黑树提高查询效率。7.2 哈希函数设计要点好的哈希函数应该计算速度快分布均匀对相似输入产生不同哈希值7.3 解决哈希冲突的方法链地址法Java HashMap使用开放地址法再哈希法8. 扩展练习建议想要真正掌握哈希表建议继续练习LC 205 同构字符串LC 290 单词模式LC 451 根据字符出现频率排序LC 347 前K个高频元素我在刷题过程中发现很多中等难度题目都是哈希表和其他数据结构如堆、双指针的结合。建议先掌握这些基础题再挑战更复杂的组合题。