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 → 输出false2.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² 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(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题的变种三数之和、四数之和问题在实际刷题过程中建议每道题都先手写实现再对比最优解。我通常会记录每种解法的时间/空间复杂度并标注易错点形成自己的解题模板。哈希表作为基础数据结构掌握其灵活应用对提升算法能力至关重要。
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 → 输出false2.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² 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(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题的变种三数之和、四数之和问题在实际刷题过程中建议每道题都先手写实现再对比最优解。我通常会记录每种解法的时间/空间复杂度并标注易错点形成自己的解题模板。哈希表作为基础数据结构掌握其灵活应用对提升算法能力至关重要。
