1. 算法训练营第五天题目解析
今天要啃下四道经典LeetCode题目：242题有效的字母异位词、349题两个数组的交集、202题快乐数，以及1题两数之和。这几道题覆盖了哈希表应用的多种典型场景，从字符串处理到数值计算，都是面试中的高频考点。我在刷题过程中发现，虽然题目描述简单，但其中藏着不少值得深究的实现细节。
1.1 题目概览与核心考点
这四道题目看似类型各异，实则都围绕着哈希表这一核心数据结构展开。242题考察字符频率统计，349题需要处理集合交集，202题涉及循环检测，而1题则是经典的查找问题。通过这组题目，我们可以系统掌握哈希表在不同场景下的应用技巧。
提示：建议按242 → 349 → 202 → 1的顺序解题，难度梯度合理，知识点衔接自然
2. 242. 有效的字母异位词
2.1 问题重述与示例分析
给定两个字符串s和t，判断t是否是s的字母异位词（即字母相同但排列顺序不同）。例如：
- 输入：s = "anagram", t = "nagaram" → 输出：true
- 输入：s = "rat", t = "car" → 输出：false
2.2 哈希表解法实现
最直观的解法是用数组模拟哈希表统计字符频率：
def isAnagram(s: str, t: str) -> bool: if len(s) != len(t): return False count = [0] * 26 for ch in s: count[ord(ch) - ord('a')] += 1 for ch in t: count[ord(ch) - ord('a')] -= 1 if count[ord(ch) - ord('a')] < 0: return False return True2.3 复杂度分析与优化
- 时间复杂度：O(n)，只需两次遍历
- 空间复杂度：O(1)，固定大小的计数数组
- 优化点：可以提前进行长度检查，避免无效计算
3. 349. 两个数组的交集
3.1 问题理解与边界处理
给定两个数组nums1和nums2，返回它们的交集（结果唯一且不考虑顺序）。例如：
- 输入：nums1 = [1,2,2,1], nums2 = [2,2] → 输出：[2]
- 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] → 输出：[9,4]
3.2 集合操作解法
利用Python的集合特性可以简洁实现：
def intersection(nums1: List[int], nums2: List[int]) -> List[int]: set1 = set(nums1) set2 = set(nums2) return list(set1 & set2)3.3 手动实现哈希表版本
如果不使用语言内置集合，可以用字典实现：
def intersection(nums1: List[int], nums2: List[int]) -> List[int]: freq = {} res = [] for num in nums1: freq[num] = freq.get(num, 0) + 1 for num in nums2: if num in freq and freq[num] > 0: res.append(num) freq[num] = 0 # 避免重复添加 return res4. 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 True4.3 数学优化思路
可以使用快慢指针法节省空间：
def isHappy(n: int) -> bool: def get_next(num): return sum(int(d)**2 for d in str(num)) slow, fast = n, get_next(n) while fast != 1 and slow != fast: slow = get_next(slow) fast = get_next(get_next(fast)) return fast == 15. 1. 两数之和
5.1 经典问题描述
给定整数数组nums和目标值target，找出和为target的两个数的索引。例如：
- 输入：nums = [2,7,11,15], target = 9 → 输出：[0,1]
- 输入：nums = [3,2,4], target = 6 → 输出：[1,2]
5.2 哈希表优化解法
暴力法需要O(n²)时间，用哈希表可优化到O(n)：
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 边界情况处理
需要特别注意：
- 数组中存在相同元素时的处理
- 无解情况的返回（题目保证有解可不处理）
- 元素为负数时的计算
6. 哈希表应用总结与对比
6.1 四道题目的哈希表使用对比
| 题目 | 哈希表作用 | 关键技巧 |
|---|---|---|
| 242 | 字符频率统计 | 数组代替哈希表 |
| 349 | 元素存在性检查 | 集合运算 |
| 202 | 循环检测 | 快慢指针优化 |
| 1 | 差值查找 | 边遍历边记录 |
6.2 常见错误与调试技巧
- 242题：未考虑unicode字符的情况（本题限定小写字母）
- 349题：结果去重处理不当
- 202题：循环终止条件设置错误
- 1题：返回索引顺序错误
注意：在面试中要主动讨论输入假设和边界条件，展示严谨性
7. 扩展练习建议
- 修改242题支持unicode字符
- 实现349题的有序输出版本
- 证明202题的非快乐数都会进入4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4的循环
- 1题的变种：三数之和、四数之和问题
在实际刷题过程中，建议每道题都先手写实现，再对比最优解。我通常会记录每种解法的时间/空间复杂度，并标注易错点形成自己的解题模板。哈希表作为基础数据结构，掌握其灵活应用对提升算法能力至关重要。
