#P4005. 三数之和
-
ID: 2207
Tried: 402
Accepted: 106
Difficulty: 5
三数之和
题目内容
给你一个整数数组nums ，判断是否存在三元组 [nums[i],nums[j],nums[k]] 满足 i!=j、i!=k 且 j!=k ，同时还满足 nums[i]+nums[j]+nums[k]==0 。请你输出所有和为 0 且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
输入描述
输入共两行。
-
第一行为两个个整数n，target，代表数组nums的长度和目标值。
-
第二行为n个整数nums0,nums1,...,numsn−1，数字之间以空格分隔。
输出描述
输出所有满足条件的三元组。 每行代表一个三元组。三元组的数字之间以空格分隔。
样例1
输入
6
-1 0 1 2 -1 -4
输出
-1 -1 2
-1 0 1
说明
nums[0]+nums[1]+nums[2]=(−1)+0+1=0。
nums[1]+nums[2]+nums[4]=0+1+(−1)=0。
nums[0]+nums[3]+nums[4]=(−1)+2+(−1)=0 。
不同的三元组是 [−1,0,1] 和 [−1,−1,2]。
注意，输出的顺序和三元组的顺序并不重要。
样例2
输入
3
0 1 1
输出
说明
唯一可能的三元组和不为 0。
样例3
输入
3
0 0 0
输出
0 0 0
说明
唯一可能的三元组和为 0。
提示
- 3<=nums.length<=3000
- −105<=nums[i]<=105
三数之和
题解思路
本题的目标是找到所有 和为 0 的 不重复三元组，并输出它们。
最直观的方法是 三重循环暴力枚举，但这样时间复杂度为 O(n³)，当 n = 3000 时会超时。
优化思路（双指针 + 排序）
- 先对数组进行排序：这样可以更方便地去重，并利用双指针减少时间复杂度。
- 固定一个数
nums[i]，然后在i右侧寻找两数之和等于-nums[i]：- 双指针法：在
nums[i]右侧，设定左指针left = i+1，右指针right = n-1，寻找满足nums[i] + nums[left] + nums[right] = 0的组合。 - 若
nums[i]和nums[i-1]相同，则跳过（避免重复）。 - 调整指针：
- 如果
nums[i] + nums[left] + nums[right] < 0，则left++使总和变大。 - 如果
nums[i] + nums[left] + nums[right] > 0，则right--使总和变小。 - 如果刚好等于
0，记录答案并跳过重复值。
- 如果
- 双指针法：在
复杂度分析
- 排序：O(n log n)
- 遍历每个元素并用双指针搜索：O(n²)
- 总时间复杂度：O(n²)（比 O(n³) 快很多，适用于本题）
- 空间复杂度：O(1)（仅使用了常数额外空间）
代码实现
Python 代码
class Solution:
def threeSum(self, nums):
"""
三数之和，双指针法
:param nums: List[int] 代表输入数组
:return: List[List[int]] 符合条件的三元组列表
"""
nums.sort() # 先排序
n = len(nums)
res = []
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]: # 跳过重复元素
continue
left, right = i + 1, n - 1 # 左右指针
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
res.append([nums[i], nums[left], nums[right]])
# 跳过重复元素
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return res
# 读取输入
if __name__ == "__main__":
n = int(input()) # 读取 n
nums = list(map(int, input().split())) # 读取数组
solution = Solution()
results = solution.threeSum(nums)
for triplet in results:
print(" ".join(map(str, triplet)))
Java 代码
import java.util.*;
public class Main {
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums); // 先排序
List<List<Integer>> res = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) { // 跳过重复元素
continue;
}
int left = i + 1, right = n - 1;
while (left < right) {
int total = nums[i] + nums[left] + nums[right];
if (total < 0) {
left++;
} else if (total > 0) {
right--;
} else {
res.add(Arrays.asList(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--;
}
}
}
return res;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 读取 n
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = scanner.nextInt();
}
scanner.close();
Main main = new Main();
Solution solution = main.new Solution();
List<List<Integer>> results = solution.threeSum(nums);
for (List<Integer> triplet : results) {
System.out.println(triplet.get(0) + " " + triplet.get(1) + " " + triplet.get(2));
}
}
}
C++ 代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 先排序
vector<vector<int>> res;
int n = nums.size();
for (int i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // 跳过重复元素
int left = i + 1, right = n - 1;
while (left < right) {
int total = nums[i] + nums[left] + nums[right];
if (total < 0) {
left++;
} else if (total > 0) {
right--;
} else {
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--;
}
}
}
return res;
}
};
int main() {
int n;
cin >> n; // 读取 n
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
Solution solution;
vector<vector<int>> results = solution.threeSum(nums);
for (const auto& triplet : results) {
cout << triplet[0] << " " << triplet[1] << " " << triplet[2] << endl;
}
return 0;
}