[Leetcode][15. 三数之和] 3种方法：暴力，Hash，双指针
By Long Luo
方法一：暴力遍历
思路与算法：
首先想到的是暴力枚举\(3\)层循环，但结果肯定会出现重复的数字，我们可以使用HashSet来去除重复元素。
值得注意的是需要先进行排序，如果不排序的话，会返回重复的答案，因为虽然List元素都相同，但顺序不同，还是重复的三元组。
代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public List<List<Integer>> threeSum(int[] nums) {
if (nums == null || nums.length < 3) {
return new ArrayList<>();
}
Set<List<Integer>> ans = new HashSet<>();
Arrays.sort(nums);
int length = nums.length;
for (int i = 0; i < length - 2; i++) {
for (int j = i + 1; j < length - 1; j++) {
for (int k = j + 1; k < length; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
ans.add(Arrays.asList(nums[i], nums[j], nums[k]));
}
}
}
}
return new ArrayList<>(ans);
}
}
上述操作会超时，而且使用了Set进行去重，可不可以不用Set呢？
如何才能保证不包含重复的三元组？
保持三重循环的大框架不变，只需要保证：
- 第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；
- 第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。
也就是说，我们枚举的三元组 \((a, b, c)\) 满足 \(a \leq b \leq c\) ，保证了只有 \((a, b, c)\) 这个顺序会被枚举到，而\((b, a, c)\) 、\((c, b, a)\) 等等这些不会，这样就减少了重复。
要实现这一点，先将数组中的元素从小到大进行排序，在每次循环中如果判断，防止出现重复的答案。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
36public List<List<Integer>> threeSum(int[] nums) {
if (nums == null || nums.length < 3) {
return new ArrayList<>();
}
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
int length = nums.length;
for (int i = 0; i < length - 2; i++) {
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < length - 1; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
for (int k = j + 1; k < length; k++) {
if (k > j + 1 && nums[k] == nums[k - 1]) {
continue;
}
if (nums[i] + nums[j] + nums[k] == 0) {
ans.add(Arrays.asList(nums[i], nums[j], nums[k]));
}
}
}
}
return ans;
}
复杂度分析
- 时间复杂度： \(O(N^3)\) ，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
- 空间复杂度： \(O(\log N)\)，额外的排序的空间复杂度为\(O(\log N)\) 。
