1. 题目链接
2. 题目描述
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
3. 题目示例
示例 1 :
输入：nums = [-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 :
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3 :
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
4. 解题思路
思路: 先排序 + 双指针
- 排序：
- 首先对输入数组进行排序，以便能够使用双指针法有效查找三元组。
- 排序后的数组有助于避免重复的三元组，因为可以跳过重复的元素。
- 枚举第一个数：
- 我们将数组中的每个元素作为第一个数
nums[first]，然后使用双指针来寻找与其相加为 0 的另外两个数。
- 双指针法：
- 对于固定的
first，我们可以用两个指针second和third来查找nums[second]和nums[third]，使得nums[first] + nums[second] + nums[third] = 0。second从first + 1开始，third从数组的末尾开始。- 如果当前三数之和大于零，则移动
third向左（减少和）。 - 如果当前三数之和小于零，则移动
second向右（增大和）。 - 如果三数之和为零，记录该三元组，并且避免重复，继续移动指针。
- 跳过重复的元素：
- 为了避免重复的三元组，我们在枚举
first和second时，跳过和上一个元素相同的值。 first > 0 && nums[first] == nums[first - 1]：如果当前first的值和前一个first的值相同，则跳过。second > first + 1 && nums[second] == nums[second - 1]：如果当前second的值和前一个second的值相同，则跳过。
- 返回结果：
- 经过两层循环和双指针操作，最终返回所有符合条件的三元组。
5. 题解代码
Java 代码 :
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int n = nums.length;
// 排序
Arrays.sort(nums);
// 枚举 A
for(int first = 0; first < n; first++){
// 与上次枚举的数不相同
if(first > 0 && nums[first] == nums[first-1]) continue;
// C的指针指向数组的末端
int third = n-1;
int target = -nums[first];
// 枚举 B
for(int second = first + 1; second < n; second++){
// 与上次枚举的数不相同
if(second > first + 1 && nums[second] == nums[second-1]) continue;
// 保证 B 的指针在 C 的左侧
while(second < third && nums[second] + nums[third] > target) third--;
// 如果 B/C 指针重叠, 则B向后移
if(second == third) break;
if(nums[second] + nums[third] == target){
List<Integer> temp = new ArrayList<>();
temp.add(nums[first]);
temp.add(nums[second]);
temp.add(nums[third]);
res.add(temp);
}
}
}
return res;
}
}
6. 复杂度分析
- 时间复杂度: 外层循环枚举第一个数
first，内层循环枚举第二个数second，并用双指针查找第三个数。每次操作的时间复杂度是 O(n)，所以总体时间复杂度是 O(n^2)。 - 空间复杂度: 我们使用了一个结果列表
res来存储三元组，最坏情况下会存储O(n^2)个三元组。 - 排序数组时需要 O(log n) 的空间来存储排序过程中的临时数据。 所以，空间复杂度是 O(n)。