1. 算法训练营第六天：哈希表实战精讲

今天咱们来啃下算法训练营的四个经典题目：字母异位词判断、数组交集、快乐数判定和两数之和。这几个题看似简单，但涵盖了哈希表最核心的应用场景，我结合自己刷题和面试官的经验，给大家拆解其中的门道。

哈希表就像个智能抽屉柜——你存东西时系统自动分配位置，取的时候直接开对应抽屉。这种O(1)时间复杂度的特性，让它成为处理"存在性检查"问题的神器。下面我会用厨房备菜的类比带大家理解每个题的本质，并给出Python和Java两种实现，连调试中的边界陷阱都给你标清楚。

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

2.1 问题本质剖析

字母异位词就像两套相同的乐高积木，拼法不同但零件完全一致。判断两个字符串是否为异位词，核心是确认：

1. 长度必须相同（零件总数相同）
2. 每个字母出现次数完全一致（每种积木块数量相同）

2.2 三种解法对比

解法一：排序比对法

def isAnagram(s: str, t: str) -> bool: return sorted(s) == sorted(t)

时间复杂度：O(nlogn)
空间复杂度：O(n)

适合短字符串，代码极简但效率不是最优

解法二：数组计数器

public boolean isAnagram(String s, String t) { if (s.length() != t.length()) return false; int[] counter = new int[26]; for (char c : s.toCharArray()) counter[c-'a']++; for (char c : t.toCharArray()) if (--counter[c-'a'] < 0) return false; return true; }

时间复杂度：O(n)
空间复杂度：O(1)（固定26长度的数组）

最优解，类似厨房备菜时给每种调料单独称重

解法三：哈希表通用版

from collections import defaultdict def isAnagram(s: str, t: str) -> bool: if len(s) != len(t): return False count = defaultdict(int) for c in s: count[c] += 1 for c in t: count[c] -= 1 if count[c] < 0: return False return True

支持Unicode等扩展场景，是解法二的通用版本

2.3 边界陷阱

1. 输入包含大写字母时要先统一大小写
2. Unicode字符处理需要扩大计数器容量
3. 空字符串特殊情况处理

3. 349. 两个数组的交集

3.1 问题变形思考

这道题有个变体版本（350题）要求统计重复次数，而本题只需要唯一交集元素。就像比较两个购物清单的共同商品，但不用关心买了多少件。

3.2 哈希集合法

def intersection(nums1, nums2): set1 = set(nums1) set2 = set(nums2) return list(set1 & set2)

时间复杂度：O(m+n)
空间复杂度：O(m+n)

内置集合运算最简洁，但隐藏了底层实现

3.3 手动实现版

public int[] intersection(int[] nums1, int[] nums2) { HashSet<Integer> set = new HashSet<>(); for (int num : nums1) set.add(num); HashSet<Integer> result = new HashSet<>(); for (int num : nums2) { if (set.contains(num)) result.add(num); } return result.stream().mapToInt(i->i).toArray(); }

显式展示了哈希表去重过程

3.4 进阶挑战

如果数组已排序，可以使用双指针法将空间复杂度降到O(1)：

def intersection(nums1, nums2): nums1.sort() nums2.sort() i = j = 0 res = [] while i < len(nums1) and j < len(nums2): if nums1[i] == nums2[j]: if not res or res[-1] != nums1[i]: res.append(nums1[i]) i += 1 j += 1 elif nums1[i] < nums2[j]: i += 1 else: j += 1 return res

4. 202. 快乐数

4.1 数学本质解析

快乐数判定其实是检测数字序列是否进入循环。就像迷宫中的老鼠，要么找到出口（变为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

时间复杂度：O(logn)
空间复杂度：O(logn)

4.3 快慢指针法

public boolean isHappy(int n) { int slow = n, fast = getNext(n); while (fast != 1 && slow != fast) { slow = getNext(slow); fast = getNext(getNext(fast)); } return fast == 1; } private int getNext(int n) { int sum = 0; while (n > 0) { int d = n % 10; sum += d * d; n /= 10; } return sum; }

空间复杂度优化到O(1)

类似链表环检测的Floyd算法

4.4 数学优化

所有不快乐数最终都会进入4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4的循环。可以利用这个规律进一步优化：

def isHappy(n): cycle = {4,16,37,58,89,145,42,20} while n != 1 and n not in cycle: n = sum(int(d)**2 for d in str(n)) return n == 1

5. 1. 两数之和

5.1 问题变体

这是LeetCode第一题，衍生出三数之和、四数之和等系列问题。核心思想都是通过哈希表减少不必要的重复计算。

5.2 哈希表解法

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 []

时间复杂度：O(n)
空间复杂度：O(n)

5.3 错误示范

// 错误代码：先填充整个哈希表 public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { map.put(nums[i], i); } for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement) && map.get(complement) != i) { return new int[]{i, map.get(complement)}; } } throw new IllegalArgumentException("No solution"); }

这种写法无法处理重复元素如[3,3]，target=6的情况

5.4 多语言实现要点

• C++：注意unordered_map的哈希冲突处理
• JavaScript：对象和Map的性能差异
• Go：需要提前make map初始化大小

6. 哈希表实战技巧

6.1 负载因子与扩容

当哈希表填充超过75%时，Java的HashMap会进行rehashing。对于性能敏感场景可以预设容量：

Map<String, Integer> map = new HashMap<>(expectedSize * 4 / 3 + 1);

6.2 哈希冲突处理

• 开放寻址法：Python字典采用
• 链地址法：Java HashMap采用
• 再哈希法：数据库系统常用

6.3 语言特性对比

6.4 高频面试考点

1. 哈希函数设计原则（一致性、均匀性、高效性）
2. 解决冲突方法的优缺点比较
3. 哈希表与平衡树的trade-off
4. 分布式哈希表(DHT)的应用场景

我在面试候选人时，最关注的是能否从具体问题抽象出哈希表的应用场景。比如最近问过"如何设计一个实时统计TOP K搜索词的系统"，期望的回答就会涉及哈希表计数+最小堆的组合使用。