-
Notifications
You must be signed in to change notification settings - Fork 417
/
Solution11.java
71 lines (70 loc) · 2.65 KB
/
Solution11.java
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
/*
* @Description
* 三数之和
* 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。
* 请你返回所有和为 0 且不重复的三元组。注意:答案中不可以包含重复的三元组。
*
* 示例 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 。
*/
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length();
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<List<Integer>>();
// 枚举 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 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环
if (second === third) {
break;
}
if (nums[second] + nums[third] == target) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[first]);
list.add(nums[second]);
list.add(nums[third]);
ans.add(list);
}
}
}
return ans;
}
}