三数之和算法：排序与双指针的经典应用

1. 三数之和问题解析

三数之和（3Sum）是LeetCode上经典的算法问题，也是面试中的高频考点。题目要求在一个整数数组中找到所有不重复的三元组，使得这三个数的和等于零。这个问题看似简单，但想要高效解决并处理好各种边界条件，需要掌握一些核心技巧。

1.1 问题定义与难点

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

这个问题的难点主要在于：

1. 如何高效地找到所有可能的三元组组合
2. 如何处理重复元素导致的重复解
3. 如何优化算法使其时间复杂度尽可能低

1.2 暴力解法分析

最直观的解法是三层循环暴力枚举所有可能的三元组组合：

def threeSum(nums): n = len(nums) result = [] 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³)，在n较大时（如n=3000）会非常慢，无法通过LeetCode的时间限制测试。

2. 优化思路：排序+双指针

2.1 排序的价值

排序是这个问题的关键第一步。将数组排序后，我们可以利用有序性来优化搜索过程：

1. 方便跳过重复元素，避免重复解
2. 可以使用双指针技巧来减少搜索空间
3. 可以利用大小关系提前终止某些搜索路径

排序的时间复杂度是O(nlogn)，这比暴力解法的O(n³)要好得多。

2.2 双指针技巧

排序后，我们可以固定一个数，然后使用双指针在剩余部分寻找另外两个数：

1. 固定nums[i]作为第一个数
2. 在i+1到n-1的范围内，设置left=i+1和right=n-1两个指针
3. 计算sum = nums[i] + nums[left] + nums[right]
   • 如果sum == 0，找到一组解
   • 如果sum < 0，需要增大总和，left++
   • 如果sum > 0，需要减小总和，right--

这种方法将内层的两层循环优化为了一层循环，整体时间复杂度降为O(n²)。

3. 代码实现详解

3.1 完整代码解析

让我们详细分析提供的C++解决方案：

class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ans; int n = nums.size(); sort(nums.begin(), nums.end()); for(int i = 0; i < n; i++){ // 跳过重复的nums[i] if(i > 0 && nums[i] == nums[i-1]) continue; int left = i + 1; int right = n - 1; int target = -nums[i]; while(left < right){ int sum = nums[left] + nums[right]; if(sum == target){ ans.push_back({nums[i], nums[left], nums[right]}); // 跳过重复的nums[left]和nums[right] while(left < right && nums[left] == nums[left+1]) left++; while(left < right && nums[right] == nums[right-1]) right--; left++; right--; } else if(sum < target){ left++; } else{ right--; } } } return ans; } };

3.2 关键点解析

1. 外层循环去重：

   if(i > 0 && nums[i] == nums[i-1]) continue;

   这行代码确保了我们不会对相同的nums[i]值重复处理，避免了外层循环产生的重复解。

2. 双指针移动逻辑：

   • 当sum == target时，我们找到一组解，然后需要跳过所有与当前left和right相同的值
   • 当sum < target时，left右移增大总和
   • 当sum > target时，right左移减小总和

3. 去重处理：

   while(left < right && nums[left] == nums[left+1]) left++; while(left < right && nums[right] == nums[right-1]) right--;

   这两行代码确保了我们不会记录相同的三元组多次，即使数组中有重复元素。

4. 常见问题与优化技巧

4.1 典型错误与修正

1. 去重时机错误：

   • 错误做法：先跳过所有重复元素，再检查sum
   • 正确做法：先找到有效解，再跳过重复元素
   • 原因：直接跳过可能会漏掉有效的三元组组合

2. 边界条件处理：

   • 数组长度小于3时应直接返回空
   • 排序后如果第一个元素已经大于0，可以直接返回（因为后面的元素更大，不可能有三数之和为0）

4.2 性能优化建议

1. 提前终止：

   if(nums[i] > 0) break;

   因为数组已排序，如果nums[i] > 0，后面的数更大，三数之和不可能为0

2. 最小化搜索空间：

   • 当nums[i] + nums[i+1] + nums[i+2] > 0时，可以提前终止
   • 当nums[i] + nums[n-2] + nums[n-1] < 0时，可以跳过当前nums[i]

3. 使用更高效的数据结构：

   • 对于某些语言，使用原生数组而非动态数组可能更快
   • 预先分配足够的结果存储空间，避免频繁扩容

5. 扩展应用与变种问题

5.1 最接近的三数之和

LeetCode 16题是这个问题的一个变种，要求找到三数之和最接近目标值的组合。可以使用类似的排序+双指针方法：

1. 排序数组
2. 初始化最接近的和
3. 固定一个数，使用双指针寻找另外两个数
4. 根据当前和与目标值的差距更新最接近的和

5.2 四数之和

LeetCode 18题将问题扩展到四个数。解决思路类似：

1. 排序数组
2. 双层循环固定前两个数
3. 使用双指针寻找后两个数
4. 注意多层去重处理

5.3 K数之和通用解法

对于K数之和问题，可以使用递归+回溯的方法：

1. 排序数组
2. 定义递归函数，每次固定一个数
3. 当固定到K-2个数时，使用双指针法找最后两个数
4. 注意各层级的去重处理

6. 面试技巧与实战建议

6.1 面试中的考察重点

面试官通常会关注：

1. 是否考虑到排序预处理的重要性
2. 能否正确实现双指针技巧
3. 如何处理重复解的问题
4. 能否分析算法的时间复杂度

6.2 白板编程建议

1. 先明确问题要求和边界条件
2. 从暴力解法开始，逐步优化
3. 重点解释排序和双指针的选择理由
4. 详细说明去重处理的逻辑
5. 主动分析时间复杂度和空间复杂度

6.3 调试技巧

1. 使用小规模测试用例验证基本逻辑
2. 特别注意全零数组、全正数/负数数组等边界情况
3. 打印中间变量检查双指针移动是否正确
4. 检查去重逻辑是否过于激进或过于宽松

在实际编码中，我发现最容易出错的地方是去重逻辑的处理顺序。一定要记住：先找到有效解，然后再跳过重复元素，而不是反过来。这个细微的差别可能会导致漏解或者产生重复解。