1. 算法训练营第六天题目解析今天我们要啃下四道经典的哈希表和双指针题目454.四数相加II、383.赎金信、15.三数之和、18.四数之和。这几道题在面试中出现频率极高也是检验基础算法能力的试金石。我结合自己刷题和面试官的经验给大家拆解其中的核心技巧和易错点。1.1 题目概览与难度分析这四道题可以分为两类技术路线哈希表专场454题统计频次和383题字符计数双指针专场15题三数之和和18题四数之和从力扣通过率来看454.四数相加II中等通过率63.2%383.赎金信简单通过率56.3%15.三数之和中等通过率36.1%18.四数之和中等通过率38.7%注意通过率低往往不是因为算法本身复杂而是边界条件处理不到位。比如三数之和的去重操作很多同学会在这里翻车。2. 哈希表问题精讲2.1 454.四数相加II问题本质在四个数组中各取一个数使abcd0统计所有可能的组合数。暴力解法陷阱 直接四重循环时间复杂度O(n⁴)当n200时运算量高达1.6亿次必定超时。优化思路# 分组哈希策略 # 把ab的和存入哈希表再查找-(cd) def fourSumCount(nums1, nums2, nums3, nums4): from collections import defaultdict hashmap defaultdict(int) count 0 # 计算ab的所有可能和 for a in nums1: for b in nums2: hashmap[a b] 1 # 查找匹配的-(cd) for c in nums3: for d in nums4: target - (c d) count hashmap.get(target, 0) return count复杂度分析时间复杂度O(n²) 两次双重循环空间复杂度O(n²) 最坏情况下ab的所有组合都不相同实战技巧使用defaultdict(int)比普通字典更简洁第二个循环中直接累加计数避免多余的if判断Python中Counter类也可以实现相同功能2.2 383.赎金信问题本质判断magazine中的字符能否组成ransomNote每个字符只能用一次。常见误区有同学先排序再比较时间复杂度O(nlogn)不够优忽略大小写敏感要求本题所有字符都是小写最优解法def canConstruct(ransomNote, magazine): from collections import defaultdict # 统计magazine字符频次 char_count defaultdict(int) for c in magazine: char_count[c] 1 # 检查ransomNote字符 for c in ransomNote: char_count[c] - 1 if char_count[c] 0: return False return True进阶技巧如果字符范围确定如只有小写字母可以用固定长度数组代替哈希表def canConstruct(ransomNote, magazine): count [0] * 26 for c in magazine: count[ord(c) - ord(a)] 1 for c in ransomNote: count[ord(c) - ord(a)] - 1 if count[ord(c) - ord(a)] 0: return False return True3. 双指针问题精讲3.1 15.三数之和问题难点需要找出所有不重复的三元组处理多个元素的去重逻辑标准解法框架def threeSum(nums): nums.sort() res [] n len(nums) for i in range(n - 2): # 去重逻辑易错点 if i 0 and nums[i] nums[i - 1]: continue left, right i 1, n - 1 while left right: total nums[i] nums[left] nums[right] if total 0: left 1 elif total 0: right - 1 else: res.append([nums[i], nums[left], nums[right]]) # 去重逻辑关键 while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 return res去重逻辑详解外层循环去重nums[i] nums[i-1]时跳过内层双指针去重找到解后跳过所有相同的nums[left]和nums[right]易错案例 输入[-2,0,0,2,2] 错误输出[[-2,0,2], [-2,0,2]] 正确输出[[-2,0,2]]3.2 18.四数之和问题升级 在三数之和基础上增加一个维度需要两层固定指针双指针解法模板def fourSum(nums, target): nums.sort() res [] n len(nums) for i in range(n - 3): # 一级去重 if i 0 and nums[i] nums[i - 1]: continue for j in range(i 1, n - 2): # 二级去重 if j i 1 and nums[j] nums[j - 1]: continue left, right j 1, n - 1 while left right: total nums[i] nums[j] nums[left] nums[right] if total target: left 1 elif total target: right - 1 else: res.append([nums[i], nums[j], nums[left], nums[right]]) # 双指针去重 while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 return res剪枝优化 在两层固定指针处可以增加提前终止条件# 第一层剪枝 if nums[i] * 4 target: break # 第二层剪枝 if nums[i] nums[j] * 3 target: break4. 高频面试问题与优化技巧4.1 哈希表问题常见变种统计频次类如454题空间换时间典型应用分组思想把O(n⁴)降为O(n²)字符匹配类如383题ASCII码数组比哈希表更高效可用Counter快速实现from collections import Counter def canConstruct(ransomNote, magazine): return not Counter(ransomNote) - Counter(magazine)4.2 双指针问题注意事项排序预处理三/四数之和必须先排序时间复杂度O(nlogn)可忽略去重三原则外层循环去重内层循环去重找到解后跳过重复元素边界条件数组长度不足直接返回最小和大于target时提前终止最大和小于target时跳过本轮4.3 性能对比实测在LeetCode测试用例上的运行时间题号测试用例规模哈希解法(ms)双指针解法(ms)454200元素数组320-153000元素数组-68018200元素数组-180实测建议哈希法在n较小时更优双指针在需要去重时更合适5. 刷题训练建议刻意练习顺序先练383简单哈希再练454分组哈希然后15经典双指针最后18双指针扩展Debug检查清单哈希表问题是否处理了空输入统计频次时是否覆盖所有情况双指针问题排序了吗去重逻辑是否正确指针移动条件是否完整ACM模式练习 很多笔试要求自己处理输入输出建议补充练习# 三数之和的ACM模式示例 import sys def main(): input sys.stdin.read().split() nums list(map(int, input[1:])) target int(input[0]) # 调用threeSum函数 result threeSum(nums) print(result) if __name__ __main__: main()我在面试候选人时发现能清晰解释去重逻辑的候选人通常对双指针法的理解更深刻。建议在白板编码时边写边说出每个去重判断的作用这会让面试官看到你的思维严谨性。