1. 算法训练营第五天题目概览今天我们要啃下四道经典算法题覆盖哈希表、双指针、数学运算等多个核心知识点。这四道题看似简单但每道都藏着值得深挖的编程思维和优化技巧。作为过来人我建议你先自己尝试解题再看解析效果会更好。242题考察字符串处理的底层逻辑349题是集合运算的典型应用202题需要发现数学规律而1题则是面试必考的哈希表应用。这四道题组合在一起正好构成一个从基础到进阶的合理训练路径。我在刷题时发现按这个顺序解题能帮助建立系统的解题思维。2. 242.有效的字母异位词深度解析2.1 问题本质与暴力解法判断两个字符串是否为字母异位词本质上是要确认它们包含的字母种类和数量完全一致。最直观的做法是用两层循环比较时间复杂度O(n²)。但作为有经验的程序员我们肯定要寻找更优解。# 暴力解法示例不推荐 def isAnagram(s: str, t: str) - bool: if len(s) ! len(t): return False for char in s: if s.count(char) ! t.count(char): return False return True2.2 哈希表优化方案使用字典统计字符频率是更聪明的做法。Python中可以用collections.defaultdict也可以直接用内置的Counterfrom collections import Counter def isAnagram(s: str, t: str) - bool: return Counter(s) Counter(t)这里有个细节要注意Counter比较时会自动处理长度不一致的情况所以可以省略长度判断。但在其他语言实现时建议先检查长度可以提前返回节省时间。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这种写法虽然代码量稍多但运行效率更高在字符串很长时优势明显。我在实际面试中遇到过面试官特别要求用数组实现的场景。3. 349.两个数组的交集解题思路3.1 集合运算的直观解法这道题要求找出两个数组中都存在的唯一元素。Python的集合操作让这道题变得非常简单def intersection(nums1, nums2): return list(set(nums1) set(nums2))但要注意几个边界情况输入数组中可能包含重复元素结果需要返回列表而非集合空数组的处理3.2 手动实现哈希表解法为了深入理解底层原理我们可以手动实现集合的交集操作def intersection(nums1, nums2): record {} result [] for num in nums1: record[num] record.get(num, 0) 1 for num in nums2: if num in record and record[num] 0: result.append(num) record[num] 0 # 避免重复添加 return result这种方法虽然代码量多但能更好地理解哈希表的工作原理。在资源受限的环境下这种可控的实现方式可能更可靠。3.3 双指针解法及比较如果输入数组已经有序可以使用双指针法def intersection(nums1, nums2): nums1.sort() nums2.sort() i j 0 result [] while i len(nums1) and j len(nums2): if nums1[i] nums2[j]: if not result or nums1[i] ! result[-1]: result.append(nums1[i]) i 1 j 1 elif nums1[i] nums2[j]: i 1 else: j 1 return result三种方法的时间复杂度比较方法时间复杂度空间复杂度适用场景集合运算O(mn)O(mn)代码简洁通用场景哈希表O(mn)O(min(m,n))需要控制内存时双指针O(mlogm nlogn)O(1)已排序或可排序的输入4. 202.快乐数的数学奥秘4.1 快乐数定义与检测方法快乐数的定义是对于一个正整数每次将该数替换为它每个位置上的数字的平方和重复这个过程直到变为1或者无限循环但始终变不到1。如果可以变为1就是快乐数。直接按照定义实现的解法def isHappy(n: int) - bool: seen set() while n ! 1: n sum(int(d)**2 for d in str(n)) if n in seen: return False seen.add(n) return True4.2 快慢指针优化这个问题实际上可以转化为检测链表是否有环的问题因此可以用快慢指针优化空间复杂度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这种方法将空间复杂度从O(n)降到了O(1)是非常巧妙的优化。我在第一次遇到这个问题时没有想到这种解法后来看到才恍然大悟。4.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这种解法利用了数学规律在实际运行中最快。它告诉我们算法优化有时需要结合数学洞察力。5. 1.两数之和的多种解法5.1 暴力枚举法最直观的方法是双重循环def twoSum(nums, target): for i in range(len(nums)): for j in range(i1, len(nums)): if nums[i] nums[j] target: return [i, j] return []虽然时间复杂度O(n²)但对于小规模数据仍然可用。在实际编程中如果确定输入规模很小简单的解法可能是更好的选择。5.2 哈希表优化解法使用哈希表可以将时间复杂度降到O(n)def twoSum(nums, target): 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 []这里有几点需要注意要先查找补数再插入当前数避免重复使用同一元素使用enumerate同时获取索引和值更Pythonic哈希表存储的是数值到索引的映射5.3 排序加双指针的变种如果题目只要求返回值而非索引可以先排序再用双指针def twoSum(nums, target): nums_sorted sorted(nums) left, right 0, len(nums) - 1 while left right: current_sum nums_sorted[left] nums_sorted[right] if current_sum target: return [nums_sorted[left], nums_sorted[right]] elif current_sum target: left 1 else: right - 1 return []这种方法时间复杂度O(nlogn)空间复杂度取决于排序实现。虽然不适用于原题但类似的变种问题中可能有用。6. 四道题的综合比较与学习建议通过这四道题我们可以总结出一些通用的解题模式哈希表是处理查找问题的利器四道题中有三道(242,349,1)都可以用哈希表显著优化数学规律能带来意外优化快乐数问题展示了数学分析的重要性不同解法适合不同场景没有绝对的最优解要根据具体需求选择我在刷题过程中总结了一些经验先理解问题本质再考虑优化多思考不同解法的时间/空间复杂度折衷注意边界条件和特殊输入实际编码前先举例验证思路对于算法初学者我建议先独立尝试解题至少思考30分钟写出暴力解法并分析复杂度思考是否有更优的数据结构可用最后参考优质题解比较思路差异这四道题看似基础但深入理解后能帮助我们建立扎实的算法思维为更复杂的问题打下基础。