1. 算法训练营第六天题目解析今天要解决的三道LeetCode题目都涉及哈希表这一核心数据结构这也是算法面试中的高频考点。242题考察字符串处理与哈希映射349题需要掌握集合操作202题则结合了数学特性与哈希检测。这三道题看似简单但都蕴含着算法设计的经典思想。1.1 题目背景与核心考点242题有效的字母异位词要求判断两个字符串的字符组成是否完全相同这是处理字符串类问题的典型代表。349题两个数组的交集需要找出两个数组中共同存在的元素考察集合操作的基本功。202题快乐数则是一个结合数学特性的有趣问题需要理解快乐数的定义并设计检测算法。这三道题共同的特点是都可以用哈希表来优化时间复杂度。哈希表通过O(1)时间复杂度的查找特性能将许多暴力解法从O(n²)优化到O(n)这是算法优化的重要思路。2. LeetCode 242. 有效的字母异位词2.1 问题描述与示例给定两个字符串s和t编写一个函数来判断t是否是s的字母异位词。字母异位词指字母相同但排列不同的字符串。示例1 输入: s anagram, t nagaram 输出: true示例2 输入: s rat, t car 输出: false2.2 哈希表解法详解最直观的解法是统计每个字符串中各个字符的出现次数然后比较两个统计结果是否相同。哈希表正是实现这一思路的理想数据结构。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这个实现中我们首先检查两个字符串长度是否相同不同则直接返回False。然后使用字典统计s中每个字符的出现次数接着遍历t中的字符相应减少计数。如果发现某个字符在t中的出现次数多于s则返回False。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: count[ord(char) - ord(a)] - 1 if count[ord(char) - ord(a)] 0: return False return True变种问题可能包括不考虑字符大小写的异位词判断允许最多k个字符不同的近似异位词在文档中查找所有异位词子串3. LeetCode 349. 两个数组的交集3.1 问题描述与示例给定两个数组nums1和nums2返回它们的交集。输出结果中的每个元素必须是唯一的不考虑输出顺序。示例1 输入nums1 [1,2,2,1], nums2 [2,2] 输出[2]示例2 输入nums1 [4,9,5], nums2 [9,4,9,8,4] 输出[9,4]3.2 集合操作解法这道题可以直接利用集合的交集操作来解决def intersection(nums1: List[int], nums2: List[int]) - List[int]: return list(set(nums1) set(nums2))对于较大的输入可以先对两个数组排序然后使用双指针法查找共同元素这样空间复杂度可以优化到O(1)。3.3 哈希表实现细节如果不使用内置集合操作可以用哈希表手动实现def intersection(nums1: List[int], nums2: List[int]) - List[int]: set1 set(nums1) result set() for num in nums2: if num in set1: result.add(num) return list(result)这种方法的时间复杂度是O(mn)空间复杂度是O(min(m,n))其中m和n分别是两个数组的长度。4. LeetCode 202. 快乐数4.1 问题描述与数学原理快乐数定义为对于一个正整数每一次将该数替换为它每个位置上的数字的平方和然后重复这个过程直到这个数变为1也可能是无限循环但始终变不到1。如果可以变为1那么这个数就是快乐数。示例 输入19 输出true 解释 1² 9² 82 8² 2² 68 6² 8² 100 1² 0² 0² 14.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(number): return sum(int(d)**2 for d in str(number)) slow n fast get_next(n) while fast ! 1 and slow ! fast: slow get_next(slow) fast get_next(get_next(fast)) return fast 1这种方法基于Floyd循环检测算法空间复杂度优化到O(1)。5. 哈希表应用总结与技巧5.1 何时使用哈希表哈希表在算法问题中主要适用于以下场景需要快速查找元素是否存在需要统计元素出现频率需要记录元素出现位置需要检测重复或循环5.2 Python中的哈希表实现Python提供了多种哈希表实现dict通用的键值对存储set仅存储键的无序集合collections.defaultdict带默认值的字典collections.Counter专门用于计数的字典5.3 常见问题与调试技巧使用哈希表时常见的问题包括忘记处理空输入哈希冲突处理不当未考虑键的类型要求空间复杂度估计错误调试时可以打印中间状态的哈希表内容检查键的类型是否一致验证哈希函数是否均匀分布6. 算法训练建议6.1 刷题路线规划建议按照以下顺序练习哈希表相关题目基础应用242, 349, 202进阶应用1(两数之和), 49(字母异位词分组)综合应用454(四数相加II), 128(最长连续序列)6.2 时间管理与练习方法每道题目建议15分钟独立思考10分钟查阅资料20分钟编写代码15分钟优化和测试定期复习已解决的题目尝试不同的解法比较时间空间复杂度。6.3 面试准备要点面试中遇到哈希表问题时明确问题要求分析暴力解法思考如何用哈希表优化讨论时间空间复杂度考虑边界情况和特殊输入