1. 算法训练营第五天题目解析今天要啃下四道经典题目242.有效的字母异位词、349.两个数组的交集、202.快乐数以及1.两数之和。这几道题覆盖了哈希表应用的多种场景从字符串处理到数学验证都是面试中的高频考点。我在刷题过程中发现很多同学容易陷入暴力解法的思维定式其实用哈希表可以优雅地解决这些问题。1.1 有效的字母异位词242题这道题要求判断两个字符串是否为字母异位词字母相同但排列不同。最直观的解法是用哈希表统计字符频率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关键点使用固定大小的数组代替哈希表因为字母数量有限。时间复杂度O(n)空间复杂度O(1)常见错误是直接比较排序后的字符串这样时间复杂度会上升到O(nlogn)。实际面试中面试官更期待看到这种空间优化的解法。1.2 两个数组的交集349题要求找出两个数组中共同的唯一元素。这道题有多种解法def intersection(nums1, nums2): # 解法1使用集合操作 return list(set(nums1) set(nums2)) # 解法2手动实现 record set(nums1) res set() for num in nums2: if num in record: res.add(num) return list(res)注意结果需要去重所以使用集合存储。如果输入数组已经排序可以使用双指针法进一步优化空间我在实际测试中发现当数组元素较多时解法2的性能更好因为避免了创建临时集合的开销。1.3 快乐数202题这道题的难点在于如何检测循环。使用哈希表记录出现过的数字即可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技巧数字转字符串处理比不断取模运算更直观。数学上可以证明这个过程要么收敛到1要么进入循环一个优化方向是使用快慢指针检测循环这样空间复杂度可以降到O(1)但代码会复杂一些。1.4 两数之和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] i return []关键点边遍历边构建哈希表只需一次遍历。时间复杂度O(n)空间复杂度O(n)暴力解法的时间复杂度是O(n²)在面试中不应该作为首选方案。这道题经常被用作哈希表应用的入门例题。2. 哈希表应用深度解析2.1 何时使用哈希表哈希表特别适合以下场景需要快速查找元素是否存在需要记录元素出现次数需要建立映射关系如两数之和需要检测重复或循环在今天的四道题中哈希表分别用于统计字符频率242题快速查找元素存在349题检测数字循环202题存储补数关系1题2.2 哈希表实现选择Python中常用的哈希表结构dict通用键值对set仅存储键defaultdict带默认值的字典Counter专门用于计数在算法题中根据需求选择合适的数据结构可以简化代码。例如242题可以用Counterfrom collections import Counter def isAnagram(s, t): return Counter(s) Counter(t)但要注意实际面试时可能需要手动实现以展示对原理的理解。2.3 空间复杂度优化技巧当键的范围有限时可以用数组代替哈希表242题中字母只有26个如果数字范围已知且不大也可以用数组这种方法可以避免哈希表的开销但要注意初始化数组大小要足够键到索引的映射要明确如ASCII码计算3. 常见错误与调试技巧3.1 边界条件处理这几道题常见的边界错误未检查输入长度242题未处理空输入349题未考虑0或负数202题未处理无解情况1题调试建议先写测试用例覆盖边界情况再实现核心逻辑3.2 Python特定问题字典访问时注意键是否存在避免KeyError集合操作会改变原始集合需要时创建副本数字转字符串有性能开销在大数据量时要注意3.3 算法选择误区新手常见错误过度依赖语言内置函数如直接调用sort忽视时间/空间复杂度的权衡不考虑输入规模对算法选择的影响建议在解题时先分析时间和空间复杂度再选择合适的数据结构。4. 进阶练习建议掌握基础解法后可以尝试这些变种242题支持Unicode字符349题结果需要保持原有顺序202题找出所有不快乐数1题找出所有可能的解这些练习可以帮助深入理解哈希表的应用场景。我在准备面试时会把每道题的多种解法都实现一遍比较它们的性能差异。