1. 三数之和问题解析

三数之和（3Sum）是LeetCode上经典的算法问题，编号为第15题。这道题要求我们在给定的整数数组中找到所有不重复的三元组，使得这三个数的和等于零。看似简单的问题背后，却蕴含着多个需要仔细处理的算法细节。

1.1 问题描述与示例

给定一个包含n个整数的数组nums，判断其中是否存在三个元素a、b、c，使得a + b + c = 0？我们需要找出所有满足条件且不重复的三元组。

示例：

输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]

1.2 问题难点分析

这道题的主要难点在于：

1. 如何高效地找到所有可能的三元组组合
2. 如何避免重复的三元组出现在结果中
3. 如何处理边界情况，如数组长度不足、所有元素相同等

2. 暴力解法与优化思路

2.1 三重循环暴力解法

最直观的解法是使用三重循环枚举所有可能的三元组组合：

def threeSum(nums): result = [] n = len(nums) for i in range(n): for j in range(i+1, n): for k in range(j+1, n): if nums[i] + nums[j] + nums[k] == 0: triplet = sorted([nums[i], nums[j], nums[k]]) if triplet not in result: result.append(triplet) return result

这种解法的时间复杂度是O(n³)，在LeetCode上会超时，无法通过所有测试用例。

2.2 排序+双指针优化思路

更高效的解法是先对数组进行排序，然后使用双指针技巧：

1. 首先对数组进行排序（O(nlogn)）
2. 遍历数组，将当前元素作为第一个数
3. 在当前元素后面的子数组中使用双指针寻找另外两个数
4. 跳过重复元素以避免重复解

3. 双指针解法详解

3.1 算法步骤拆解

def threeSum(nums): nums.sort() result = [] 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: result.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 result

3.2 时间复杂度分析

• 排序：O(nlogn)
• 外层循环：O(n)
• 内层双指针：O(n)
• 总体时间复杂度：O(nlogn) + O(n²) = O(n²)

这比暴力解法的O(n³)有了显著提升。

4. 关键细节与边界处理

4.1 去重处理技巧

去重是这道题最容易出错的地方，需要在三个地方进行去重：

1. 外层循环的起始元素去重
2. 找到解后左指针的去重
3. 找到解后右指针的去重

4.2 提前终止条件

在某些情况下可以提前终止循环：

• 当nums[i] > 0时，由于数组已排序，后面的数都更大，不可能有三数之和为0
• 当nums[i] + nums[i+1] + nums[i+2] > 0时，最小的三个数之和已经大于0

4.3 特殊输入处理

需要考虑的特殊情况包括：

• 数组长度小于3
• 数组全为0
• 数组中没有满足条件的三元组

5. 算法优化与变种

5.1 使用哈希表辅助

虽然双指针是更优解，但也可以使用哈希表来实现：

def threeSum(nums): nums.sort() result = [] n = len(nums) for i in range(n): if i > 0 and nums[i] == nums[i-1]: continue target = -nums[i] seen = set() for j in range(i+1, n): complement = target - nums[j] if complement in seen: result.append([nums[i], complement, nums[j]]) while j + 1 < n and nums[j] == nums[j+1]: j += 1 seen.add(nums[j]) return result

5.2 三数之和的变种问题

掌握三数之和的解法后，可以解决一系列类似问题：

• 最接近的三数之和（16题）
• 四数之和（18题）
• 三数之和的多种组合

6. 常见错误与调试技巧

6.1 典型错误案例

1. 忘记排序数组
2. 去重逻辑不完整
3. 双指针移动条件错误
4. 边界条件处理不当

6.2 调试建议

• 使用小规模测试用例手动验证
• 打印中间变量检查指针移动和求和过程
• 特别注意去重逻辑的执行情况

7. 实际应用场景

三数之和算法在实际中有多种应用：

• 统计分析和数据挖掘中的组合查找
• 金融领域的投资组合分析
• 游戏开发中的碰撞检测和物理模拟

掌握这类算法不仅能帮助通过技术面试，更能培养解决实际问题的思维方式。这道题之所以成为LeetCode经典，正是因为它完美展现了如何通过算法优化将不可行的问题变为可行。