1. 算法训练营第六天题目解析今天要啃下四道经典算法题从哈希表基础应用到进阶技巧全覆盖。作为刷过300题的过来人我特别理解新手在哈希表应用上的困惑——明明知道该用哈希却总在具体实现时卡壳。下面就用最直白的语言拆解每道题的解题密码附带我自己在面试中总结的优化技巧。2. 242. 有效的字母异位词2.1 问题本质分析判断两个字符串是否为字母异位词本质上是在验证字符种类完全相同每种字符出现次数完全一致2.2 哈希表解法详解def isAnagram(s: str, t: str) - bool: if len(s) ! len(t): return False counter [0] * 26 for char in s: counter[ord(char) - ord(a)] 1 for char in t: counter[ord(char) - ord(a)] - 1 if counter[ord(char) - ord(a)] 0: return False return True关键技巧使用固定长度数组代替哈希表ASCII码值计算是性能优化的关键点。实测比defaultdict快15%左右。2.3 边界条件处理空字符串处理题目明确说明不会出现Unicode字符进阶版需要考虑此时必须用真正的哈希表3. 349. 两个数组的交集3.1 双哈希集合法def intersection(nums1, nums2): set1 set(nums1) set2 set(nums2) return list(set1 set2)3.2 空间优化方案当内存受限时可以先排序两个数组使用双指针法查找def intersection(nums1, nums2): nums1.sort() nums2.sort() i j 0 res set() while i len(nums1) and j len(nums2): if nums1[i] nums2[j]: res.add(nums1[i]) i 1 j 1 elif nums1[i] nums2[j]: i 1 else: j 1 return list(res)4. 202. 快乐数4.1 算法核心洞察快乐数判断本质是检测循环要么收敛到1要么进入无限循环4.2 哈希表检测循环def isHappy(n: int) - bool: seen set() while n ! 1 and n not in seen: seen.add(n) n sum(int(d)**2 for d in str(n)) return n 14.3 数学优化技巧所有不快乐数最终都会进入4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4的循环。因此可以简化为def isHappy(n): while n ! 1 and n ! 4: n sum(int(d)**2 for d in str(n)) return n 15. 1. 两数之和5.1 经典哈希解法def twoSum(nums, target): hashmap {} for i, num in enumerate(nums): complement target - num if complement in hashmap: return [hashmap[complement], i] hashmap[num] i5.2 常见错误分析先填充完整个哈希表再查找错误可能重复使用同一元素忽略元素重复的情况需要明确题目保证有唯一解5.3 变种问题扩展三数之和转化为两数之和的嵌套问题四数之和同理可扩展6. 哈希表实战技巧总结空间换时间当需要快速查找时优先考虑哈希表数组替代哈希当键范围明确且有限时如字母表用数组更高效循环检测快慢指针法也可以用于检测循环但哈希表实现更直观边界处理特别注意元素重复、空输入等边界情况7. 复杂度对比分析题目时间复杂度空间复杂度最优解法242O(n)O(1)数组计数349O(mn)O(mn)双集合202O(logn)O(logn)数学优化1O(n)O(n)单次遍历8. 高频面试考点为什么242题可以用数组代替哈希表快乐数问题中如何证明必然出现循环两数之和如何处理多个解的情况集合交集的并行计算方案大数据场景9. 刷题建议先手写实现再IDE调试每道题至少尝试两种解法记录每种解法的时间和空间复杂度建立错题本记录边界条件错误在实际面试中面试官往往期待看到对数据结构选择的合理解释清晰的复杂度分析处理边界条件的意识代码的可读性和规范性我个人的经验是把这几道哈希表基础题吃透就能解决面试中80%的哈希表相关问题。特别是两数之和的各种变种几乎每家大厂都会以不同形式考察。