最后编辑于2025-06-22
Medium
给定一个整数数组 nums，找出所有满足 nums[i] + nums[j] + nums[k] == 0 且 i, j, k 互不相同的三元组。返回的结果中不得包含重复三元组。
示例 1：
输入： nums = [-1,0,1,2,-1,-4]
输出： [[-1,-1,2],[-1,0,1]]
示例 2：
输入： nums = [0,1,1]
输出： []
示例 3：
输入： nums = [0,0,0]
输出： [[0,0,0]]
约束：
3 <= nums.length <= 3000 -10^5 <= nums[i] <= 10^5
思路与优化（排序 + 双指针）
常见解法是先对数组排序，然后枚举第一个数 nums[k]（作为固定项），在它之后使用双指针在有序数组中寻找两数之和等于 -nums[k] 的组合。关键点如下：
- 排序：让双指针可以线性地向中间收缩寻找满足和的两数对。
- 剪枝：当固定项
nums[k] > 0 时可直接停止枚举（因为后续均为正数，不可能凑出 0）。
- 去重：跳过相同的固定项
nums[k]，以及找到解后跳过左右指针相同的元素，避免重复三元组。
- 双指针移动规则：若
nums[i] + nums[j] < target 则 ++i，若大于则 --j，等于则记录并同时移动两边（并跳过重复元素）。
该方法时间复杂度为 O(n^2)，空间复杂度 O(1)（忽略答案空间）。
C++ 实现（排序 + 双指针，推荐）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
if (nums.size() < 3) return res;
for (int k = 0; k < (int)nums.size() - 2; ++k) {
if (nums[k] > 0) break;
if (k > 0 && nums[k] == nums[k - 1]) continue;
int target = -nums[k];
int i = k + 1, j = nums.size() - 1;
while (i < j) {
int sum = nums[i] + nums[j];
if (sum == target) {
res.push_back({nums[k], nums[i], nums[j]});
while (i < j && nums[i] == nums[i + 1]) ++i;
while (i < j && nums[j] == nums[j - 1]) --j;
++i; --j;
} else if (sum < target) ++i;
else --j;
}
}
return res;
}
};
|
备选：使用集合去重（代码简洁但常数因子大）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>> res;
sort(nums.begin(), nums.end());
for (int k = 0; k < (int)nums.size() - 2; ++k) {
int target = -nums[k];
int i = k + 1, j = nums.size() - 1;
while (i < j) {
int sum = nums[i] + nums[j];
if (sum == target) {
res.insert({nums[k], nums[i], nums[j]});
while (i < j && nums[i] == nums[i + 1]) ++i;
while (i < j && nums[j] == nums[j - 1]) --j;
++i; --j;
} else if (sum < target) ++i;
else --j;
}
}
return vector<vector<int>>(res.begin(), res.end());
}
};
|
作者想说的话：
排序 + 双指针是解决三数之和的经典做法：先固定一个数，再在剩余有序区间内用左右指针线性搜索，两端去重配合剪枝能把重复和无效情况过滤掉，复杂度可控且实现不复杂。
