1. 算法训练营第七天实战解析今天我们要啃下四块硬骨头454.四数相加II、383.赎金信、15.三数之和以及18.四数之和。这几个题目在面试中出现频率极高特别是三数之和系列问题堪称算法界的明星考题。我在大厂面试时曾被连续追问三数之和的三种不同解法现场手撕代码的经历至今记忆犹新。2. 454.四数相加II的哈希妙用2.1 问题本质分析给定四个整数数组nums1、nums2、nums3、nums4我们需要统计有多少个元组(i,j,k,l)满足nums1[i] nums2[j] nums3[k] nums4[l] 0。题目看似复杂实则暗藏玄机。关键突破点将O(n⁴)暴力解法优化为O(n²)的哈希解法2.2 哈希表分治策略我常用的解题模板如下def fourSumCount(nums1, nums2, nums3, nums4): from collections import defaultdict hashmap defaultdict(int) # 分组计算前两个数组的和 for n1 in nums1: for n2 in nums2: hashmap[n1 n2] 1 count 0 # 检查后两个数组的和是否匹配 for n3 in nums3: for n4 in nums4: key - (n3 n4) if key in hashmap: count hashmap[key] return count2.3 复杂度优化要点空间换时间使用哈希表存储中间结果分组策略将4数问题拆解为2个2数问题边界处理注意整数溢出情况特别是C实现时3. 383.赎金信的字符统计艺术3.1 问题建模判断ransomNote是否能由magazine中的字符组成每个字符只能使用一次。这本质上是字符频率的包含关系检查。3.2 两种高效解法对比数组计数法推荐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 True哈希表法from collections import defaultdict def canConstruct(ransomNote, magazine): magazine_counts defaultdict(int) for c in magazine: magazine_counts[c] 1 for c in ransomNote: magazine_counts[c] - 1 if magazine_counts[c] 0: return False return True3.3 性能选择建议当字符集明确且有限时如仅小写字母数组法更优处理Unicode字符等大字符集时哈希表更合适4. 15.三数之和的双指针经典4.1 问题难点剖析找出所有不重复的三元组使其和为0。这比两数之和复杂在于需要去重需要返回所有可能组合而非索引O(n³)暴力解法不可接受4.2 标准解法步骤排序数组O(nlogn)固定第一个数nums[i]对nums[i1:]使用双指针寻找两数之和等于-nums[i]def threeSum(nums): nums.sort() res [] for i in range(len(nums)-2): if i 0 and nums[i] nums[i-1]: continue l, r i1, len(nums)-1 while l r: s nums[i] nums[l] nums[r] if s 0: l 1 elif s 0: r - 1 else: res.append([nums[i], nums[l], nums[r]]) while l r and nums[l] nums[l1]: l 1 while l r and nums[r] nums[r-1]: r - 1 l 1 r - 1 return res4.3 易错点警示去重时机外层循环和内层循环都需要去重指针移动找到解后需要同时移动左右指针边界条件数组长度不足3时的处理5. 18.四数之和的通用解法5.1 问题升级挑战在三数之和基础上增加一个维度要求找出所有唯一四元组使其和等于target。5.2 解法框架扩展def fourSum(nums, target): nums.sort() res [] for i in range(len(nums)-3): if i 0 and nums[i] nums[i-1]: continue for j in range(i1, len(nums)-2): if j i1 and nums[j] nums[j-1]: continue l, r j1, len(nums)-1 while l r: s nums[i] nums[j] nums[l] nums[r] if s target: l 1 elif s target: r - 1 else: res.append([nums[i], nums[j], nums[l], nums[r]]) while l r and nums[l] nums[l1]: l 1 while l r and nums[r] nums[r-1]: r - 1 l 1 r - 1 return res5.3 剪枝优化技巧提前终止当最小和大于target或最大和小于target时跳过层级剪枝在i和j层都可以进行提前判断去重优化跳过连续相同元素6. 通用解题模式总结6.1 N数之和模板排序数组N ≥ 3时外层N-2层循环最内层使用双指针每层都需要去重处理6.2 复杂度对比表问题类型暴力解法优化解法两数之和O(n²)O(n)哈希三数之和O(n³)O(n²)双指针四数之和O(n⁴)O(n³)双指针N数之和O(n^N)O(n^(N-1))6.3 面试实战建议先明确问题条件和边界从暴力解法开始说明逐步提出优化思路特别注意去重逻辑的解释讨论可能的变种问题如最接近的三数之和我在实际面试中遇到过这些问题的多种变体比如要求返回索引而非数值或者允许重复使用元素。掌握核心思想后这些变种都能迎刃而解。建议在LeetCode上把三数之和相关的所有题目都刷一遍形成肌肉记忆。
