三数之和问题的高效解法：双指针技巧详解
问题描述
三数之和（3Sum）是一个经典的算法问题：给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a, b, c，使得 a + b + c = 0？找出所有满足条件且不重复的三元组。
解决方案思路
1. 核心思路
这个问题最直接的暴力解法需要 O(n³) 的时间复杂度，显然是不可取的。本文介绍的解决方案采用了以下优化策略：
排序：首先将数组排序，这样可以将时间复杂度降低到 O(n²)
固定一个数：遍历数组，每次固定一个数 nums[i]
双指针查找：使用左右指针在固定数右侧的区间内查找另外两个数
2. 算法步骤
cpp
vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> res; sort(nums.begin(), nums.end()); // 1. 排序 int n = nums.size(); for (int i = 0; i < n; ++i) { // 2. 提前终止：如果当前数大于0，三数之和不可能为0 if (nums[i] > 0) break; // 3. 去重：跳过重复的固定数 if (i > 0 && nums[i] == nums[i-1]) continue; // 4. 双指针查找 int left = i + 1; int right = n - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { // 找到有效三元组 res.push_back({nums[i], 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 < 0) { left++; // 和太小，左指针右移 } else { right--; // 和太大，右指针左移 } } } return res; }关键点解析
1. 排序的重要性
排序是此算法的基础，它带来了三个好处：
可以使用双指针技巧将查找两个数的时间复杂度从 O(n²) 降为 O(n)
便于去重操作
可以提前终止搜索（当固定数大于0时）
2. 去重处理
去重是解决三数之和问题的关键，代码中实现了两种去重：
固定数的去重：
cpp
if (i > 0 && nums[i] == nums[i-1]) continue;
跳过相同的固定数，避免重复的三元组。
左右指针的去重：
cpp
while (left < right && nums[left] == nums[left+1]) left++; while (left < right && nums[right] == nums[right-1]) right--;
在找到有效三元组后，跳过左右指针指向的重复值。
3. 双指针的移动逻辑
当三数之和等于0时，记录结果并同时移动左右指针
当三数之和小于0时，说明需要更大的数，左指针右移
当三数之和大于0时，说明需要更小的数，右指针左移
复杂度分析
时间复杂度
排序：O(n log n)
外层循环：O(n)
内层双指针循环：O(n)
总体：O(n²)
空间复杂度
除了输出结果外，只使用了常量级额外空间：O(1)
如果考虑存储结果的空间：O(k)，其中 k 是结果数量
示例演示
以数组[-1, 0, 1, 2, -1, -4]为例：
排序后：
[-4, -1, -1, 0, 1, 2]固定 -4，在 [-1, -1, 0, 1, 2] 中查找两数之和为4 → 无解
固定第二个 -1（跳过第一个 -1 的重复），在 [-1, 0, 1, 2] 中查找两数之和为1
找到 [-1, 0, 1] 和 [-1, -1, 2]
边界情况考虑
数组长度小于3：直接返回空结果
所有数都为正或都为负：不可能有三数之和为0
大量重复元素：去重逻辑确保结果不重复
溢出问题：虽然题目未明确，但实际应用中需要考虑整数溢出
扩展与变种
最接近的三数之和：找到和与目标最接近的三个数
四数之和：类似的思路可以扩展到四数之和问题
三数之和为任意目标值：将0改为任意目标值
总结
三数之和问题展示了如何通过排序和双指针技巧将 O(n³) 的暴力解法优化到 O(n²)。这个解决方案的关键在于：
排序预处理
固定一个数转化为两数之和问题
双指针高效查找
仔细处理去重逻辑