排序后固定第一个数，剩余区间用双指针，跳过相同值去重，O(n²)。
OJ: leetcodecn
题目 ID: 3sum
难度:普及+/提高
标签:双指针排序数组cpppython
日期: 2026-07-28 22:03
题意
找出数组中所有和为 0 且不重复的三元组。
思路
三重循环枚举 O(n³) 会超时。排序后固定第一个数，在剩余区间中用双指针寻找两数之和等于 -nums[i]。
去重是关键：排序后，每层循环（第一个数、左指针、右指针）在移动时跳过相同值，避免重复三元组。
代码
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
*/
// main.cpp：排序 + 固定第一个数 + 双指针，O(n²)。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int> &nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
int n = nums.size();
for (int i = 0; i < n - 2; i++) {
if (i && nums[i] == nums[i - 1])
continue;
int l = i + 1, r = n - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum == 0) {
ans.push_back({nums[i], nums[l], nums[r]});
while (l < r && nums[l] == nums[l + 1])
l++;
while (l < r && nums[r] == nums[r - 1])
r--;
l++;
r--;
} else if (sum < 0)
l++;
else
r--;
}
}
return ans;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int &x : a)
cin >> x;
auto ans = Solution().threeSum(a);
for (auto &v : ans) {
for (int x : v)
cout << x << ' ';
cout << '\n';
}
return 0;
}python
#!/usr/bin/env python3
from typing import List
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
ans = []
for i in range(n - 2):
if i and nums[i] == nums[i - 1]:
continue
l, r = i + 1, n - 1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s == 0:
ans.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l + 1]:
l += 1
while l < r and nums[r] == nums[r - 1]:
r -= 1
l += 1
r -= 1
elif s < 0:
l += 1
else:
r -= 1
return ans
def main() -> None:
n = int(input())
nums = list(map(int, input().split()))
ans = Solution().threeSum(nums)
for v in ans:
print(*v)
if __name__ == "__main__":
main()复杂度
- 时间复杂度：O(n²)，排序 O(n log n)，双指针 O(n²)。
- 空间复杂度：O(1)，不计答案空间。
总结
三数之和是两数之和的推广：固定一个数转化为两数之和问题，再套用双指针。排序辅助去重的做法比用哈希集合去重更干净。