哈希表算法实战：从基础到LeetCode经典题解-平芜编程栈

1. 哈希表算法复健：从基础到实战

今天咱们聊聊哈希表这个数据结构在算法题中的应用。作为算法工程师日常必备技能，哈希表能高效解决很多看似复杂的问题。我挑选了LeetCode上4道经典题目（242、349、202、1），通过它们带你彻底掌握哈希表的应用场景和实现技巧。

哈希表本质上是通过哈希函数将键映射到存储位置的数据结构，平均情况下能实现O(1)时间复杂度的查找操作。在实际算法题中，它特别适合处理需要快速判断元素是否存在、统计元素出现次数这类需求。下面我会结合具体题目，展示如何用哈希表优雅解题。

2. LC 242. 有效的字母异位词

2.1 问题重述

给定两个字符串s和t，判断t是否是s的字母异位词（即字母相同但排列不同）。例如：

输入: s = "anagram", t = "nagaram" 输出: true

2.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 True

2.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 res

4. LC 202. 快乐数

4.1 问题定义

快乐数定义为：对于一个正整数，每次将该数替换为它每个位置上的数字的平方和，重复这个过程直到结果为1（此时就是快乐数），或者无限循环但始终变不到1。

示例：

输入：19 输出：true 解释： 1² + 9² = 82 8² + 2² = 68 6² + 8² = 100 1² + 0² + 0² = 1

4.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 True

4.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 == 1

5. 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和HashSet
C++中unordered_map和unordered_set

6.2 常见应用场景

快速查找元素是否存在
统计元素出现频率
记录元素位置或状态
检测循环或重复

6.3 性能优化要点

预估数据规模，初始化合适容量
考虑哈希冲突的影响
在时间和空间之间权衡
利用语言特性（如Python的集合操作）

7. 高频面试问题解析

7.1 哈希表底层实现原理

大多数语言中的哈希表使用数组+链表/红黑树实现。当哈希冲突时，会在同一个桶中使用链表存储，当链表过长时可能转为红黑树提高查询效率。

7.2 哈希函数设计要点

好的哈希函数应该：

计算速度快
分布均匀
对相似输入产生不同哈希值

7.3 解决哈希冲突的方法

链地址法（Java HashMap使用）
开放地址法
再哈希法

8. 扩展练习建议

想要真正掌握哈希表，建议继续练习：

LC 205 同构字符串
LC 290 单词模式
LC 451 根据字符出现频率排序
LC 347 前K个高频元素

我在刷题过程中发现，很多中等难度题目都是哈希表和其他数据结构（如堆、双指针）的结合。建议先掌握这些基础题，再挑战更复杂的组合题。

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