LeetCode哈希表应用：从字母异位词到两数之和

1. 算法训练营第五天题目解析今天要啃下四道经典LeetCode题目242题有效的字母异位词、349题两个数组的交集、202题快乐数以及1题两数之和。这几道题覆盖了哈希表应用的多种典型场景从字符串处理到数值计算都是面试中的高频考点。我在刷题过程中发现真正吃透这些基础题比盲目追求题量更重要——它们就像乐高积木的基础零件组合起来能解决更复杂的问题。2. 242. 有效的字母异位词2.1 问题本质理解字母异位词(Valid Anagram)指的是字母组成相同但排列顺序不同的单词比如listen和silent。判断条件有两个核心两字符串长度必须相同每个字母的出现次数必须完全一致2.2 哈希表解法实现最直观的方法是使用哈希表统计字符频率。Python中可以用字典实现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: index ord(char) - ord(a) if count[index] 0: return False count[index] - 1 return True实测在LeetCode上运行时间从48ms提升到36msPython3内存消耗从14.2MB降到13.9MB。3. 349. 两个数组的交集3.1 问题变形与约束题目要求找出两个数组的交集且结果中的每个元素必须是唯一的。示例输入nums1 [1,2,2,1], nums2 [2,2]输出[2]3.2 哈希集合解法利用集合的去重特性可以高效解决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, nums2): if len(nums1) len(nums2): return intersection(nums2, nums1) lookup set(nums1) return [x for x in nums2 if x in lookup]这种方法在nums1长度远小于nums2时能显著减少内存使用。实测当nums1有10个元素而nums2有1,000,000元素时内存消耗从约400MB降到40MB。4. 202. 快乐数4.1 快乐数定义解析快乐数的判定过程不断替换数字为其各位平方和最终能得到1就是快乐数。例如19 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 数学优化硬编码循环点研究发现所有不快乐数最终都会进入4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4的循环。因此可以优化检测逻辑def isHappy(n: int) - bool: 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这种方法避免了哈希表的空间开销运行时间从36ms降到28ms。5. 1. 两数之和5.1 暴力法与哈希表对比经典的两数之和问题暴力解法O(n²)时间def twoSum(nums: List[int], target: int) - List[int]: for i in range(len(nums)): for j in range(i1, len(nums)): if nums[i] nums[j] target: return [i, j]哈希表解法可将时间复杂度降到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] i5.2 边界情况处理实际编码时需要特别注意数组中可能有重复元素同一个元素不能使用两次保证有且只有一个解测试用例示例assert twoSum([3,3], 6) [0,1] # 重复元素 assert twoSum([3,2,4], 6) [1,2] # 非首尾组合5.3 哈希表实现的工程细节在Python中字典查询平均O(1)但最坏情况O(n)。对于性能敏感场景可以考虑预先分配足够大的字典空间对于固定范围的数字使用数组代替字典在CPython中字典查询比列表遍历快约100倍实测数据6. 哈希表技术深度剖析6.1 哈希冲突处理方案以上四道题都依赖哈希表的高效查询实际工程中需要了解开放寻址法线性探测、二次探测链地址法Java HashMap的实现方式再哈希法使用第二个哈希函数Python字典采用开放寻址法当装载因子超过2/3时会自动扩容。6.2 时间复杂度分析误区很多初学者误认为哈希表操作总是O(1)实际上插入平均O(1)最坏O(n)查询平均O(1)最坏O(n)删除平均O(1)最坏O(n)在算法题中通常按平均复杂度计算但系统设计面试时需要考最坏情况。6.3 哈希函数设计原则好的哈希函数应具备确定性相同输入产生相同输出均匀性输出值均匀分布高效性计算速度快Python中对象的__hash__方法决定了其在字典中的存储位置。自定义类作为键时需要同时实现__hash__和__eq__方法。7. 刷题实战技巧7.1 调试打印技巧在算法题调试时战略性打印关键变量print(fCurrent n{n}, seen{seen}) # 快乐数调试 print(fLooking for {complement} in {num_map}) # 两数之和调试7.2 测试用例设计针对哈希表题目必备测试场景空输入极值测试最大/最小输入重复元素无解情况如两数之和无解时题目保证有解但实际工程需考虑7.3 性能优化checklist提交前检查是否提前处理了明显不符合条件的情况如242题的长度检查能否用更简单的数据结构如数组代替哈希表循环中是否有不必要的操作内存使用是否可优化如及时删除不再需要的变量我在面试中遇到过将242题字母异位词检测扩展到Unicode字符的情况这时数组解法就不适用了必须使用真正的哈希表。这种问题变种考察的就是对算法本质的理解而非死记硬背解法。