yicong@algo:~/code/02-two-pointers$ cat 0015-3sum.cpp
15. 三数之和
// 思路
排序后固定第一个数 nums[x],在它右侧用左右指针找两数之和为 -nums[x]: sum < 0 说明 left 太小,left++;sum > 0 说明 right 太大,right--; 命中后同时移动两个指针并跳过重复值。外层跳过重复的 x,保证三元组不重复。 剪枝:nums[x] > 0 时后面不可能再凑出 0,直接结束; nums[x] 加最大的两个数仍 < 0 时,当前 x 无解,跳过内层。
// 时间复杂度
O(n^2),排序 O(n log n),外层 n 次、每次双指针 O(n)
// 空间复杂度
O(log n)(排序递归栈,不计返回结果;答案本身最坏 O(n^2))
// 易错点
1) 去重要和「身后已处理的位置」比:x 比 x-1、left 比 left-1、right 比 right+1; 和身前比会漏解,例如 [-1,-1,2] 的 x、[-2,1,1] 的 left/right 2) left 的去重要带 left > x+1,否则会把 nums[x] 误当成前一个 left 3) x > 0 防 nums[x-1] 越界,right < n-1 防 nums[right+1] 越界
// 面试口述要点
排序提供单调性,固定最小数后两数之和用双指针 O(n) 解决, 整体从 O(n^3) 降到 O(n^2);若题目要求原下标则不能排序(见 1. 两数之和)
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
int n = (int)nums.size();
for (int x = 0; x < n - 2; ++x) {
if (nums[x] > 0) break; // 最小的数已为正,后面不可能凑出 0
if (x > 0 && nums[x] == nums[x - 1]) continue; // 固定数去重
// 当前 x 加上最大的两个数仍小于 0,内层双指针不可能有解
if (nums[x] + nums[n - 2] + nums[n - 1] < 0) continue;
int left = x + 1;
int right = n - 1;
while (left < right) {
if (left > x + 1 && nums[left] == nums[left - 1]) {
++left;
continue;
}
if (right < n - 1 && nums[right] == nums[right + 1]) {
--right;
continue;
}
int sum = nums[x] + nums[left] + nums[right];
if (sum < 0) {
++left;
} else if (sum > 0) {
--right;
} else {
ans.push_back({nums[x], nums[left], nums[right]});
++left;
--right;
}
}
}
return ans;
}
};
// 本地测试:输入 n,然后 n 个整数;每行输出一个三元组
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
vector<int> nums(n);
for (int& x : nums) cin >> x;
vector<vector<int>> ans = Solution().threeSum(nums);
for (auto& t : ans) cout << t[0] << ' ' << t[1] << ' ' << t[2] << '\n';
return 0;
}