给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
1
2
3
4
5
6
7
8
| 输入：nums =
输出：
解释：
nums + nums + nums = (-1) + 0 + 1 = 0 。
nums + nums + nums = 0 + 1 + (-1) = 0 。
nums + nums + nums = (-1) + 2 + (-1) = 0 。
不同的三元组是 和 。
注意，输出的顺序和三元组的顺序并不重要。
|
示例 2：
1
2
3
| 输入：nums =
输出：
解释：唯一可能的三元组和不为 0 。
|
示例 3：
1
2
3
| 输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
|
提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
解题思路
双指针法
在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。
接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。
如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
代码
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
26
27
28
29
30
31
32
33
| class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0; i < nums.length - 1; i++){
int left = i + 1;
int right = nums.length - 1;
if(nums[i] > 0){
break;
}
if(i > 0 && nums[i] == nums[i-1]){
continue;
}
while(left < right){
if(left < right && nums[i] + nums[left] + nums[right] > 0){
right --;
}else if(left < right && nums[i] + nums[left] + nums[right] < 0){
left ++;
}else{
Collections.addAll(path, nums[i], nums[left], nums[right]);
ans.add(new ArrayList<>(path));
path.clear();
while(left < right && nums[right] == nums[right-1]) right--;
while(left < right && nums[left] == nums[left+1]) left++;
right --;
left ++;
}
}
}
return ans;
}
}
|
- 时间复杂度: $O(n^2)$
- 空间复杂度: $O(1)$