哈希与双指针：四数相加与三数之和算法精解

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 count

2.3 复杂度优化要点

1. 空间换时间：使用哈希表存储中间结果
2. 分组策略：将4数问题拆解为2个2数问题
3. 边界处理：注意整数溢出情况（特别是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 True

3.3 性能选择建议

• 当字符集明确且有限时（如仅小写字母），数组法更优
• 处理Unicode字符等大字符集时，哈希表更合适

4. 15.三数之和的双指针经典

4.1 问题难点剖析

找出所有不重复的三元组，使其和为0。这比两数之和复杂在于：

1. 需要去重
2. 需要返回所有可能组合而非索引
3. O(n³)暴力解法不可接受

4.2 标准解法步骤

1. 排序数组（O(nlogn)）
2. 固定第一个数nums[i]
3. 对nums[i+1:]使用双指针寻找两数之和等于-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 = i+1, 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[l+1]: l += 1 while l < r and nums[r] == nums[r-1]: r -= 1 l += 1 r -= 1 return res

4.3 易错点警示

1. 去重时机：外层循环和内层循环都需要去重
2. 指针移动：找到解后需要同时移动左右指针
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(i+1, len(nums)-2): if j > i+1 and nums[j] == nums[j-1]: continue l, r = j+1, 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[l+1]: l += 1 while l < r and nums[r] == nums[r-1]: r -= 1 l += 1 r -= 1 return res

5.3 剪枝优化技巧

1. 提前终止：当最小和大于target或最大和小于target时跳过
2. 层级剪枝：在i和j层都可以进行提前判断
3. 去重优化：跳过连续相同元素

6. 通用解题模式总结

6.1 N数之和模板

1. 排序数组（N ≥ 3时）
2. 外层N-2层循环
3. 最内层使用双指针
4. 每层都需要去重处理

6.2 复杂度对比表

6.3 面试实战建议

1. 先明确问题条件和边界
2. 从暴力解法开始说明
3. 逐步提出优化思路
4. 特别注意去重逻辑的解释
5. 讨论可能的变种问题（如最接近的三数之和）

我在实际面试中遇到过这些问题的多种变体，比如要求返回索引而非数值，或者允许重复使用元素。掌握核心思想后，这些变种都能迎刃而解。建议在LeetCode上把三数之和相关的所有题目都刷一遍，形成肌肉记忆。