[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)\) 。
方法二：HashSet
方法一会超时，排序之后，很容易发现如果我们使用\(2\)层循环，遍历数组，很明显就回到了 1. 两数之和 。
使用一个Set来存储数组元素，记得用Set对结果进行去重。
代码如下所示：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
30public 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 len = nums.length;
for (int i = 0; i < len - 2; i++) {
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int target = -nums[i];
Set<Integer> set = new HashSet<>();
for (int j = i + 1; j < len; j++) {
if (set.contains(target - nums[j])) {
ans.add(Arrays.asList(nums[i], nums[j], target - nums[j]));
} else {
set.add(nums[j]);
}
}
}
return new ArrayList<>(ans);
}
复杂度分析
- 时间复杂度：\(O(N^2)\)，其中N是数组\(\textit{nums}\)的长度。
- 空间复杂度：\(O(N)\)。
方法三：双指针
思路与算法：
方法二的空间复杂度\(O(N)\) ，有没有更好的方法呢？
可以使用双指针，将时间复杂度从 \(O(N^2)\) 减少至\(O(N)\) 。
在枚举的过程每一步中，左指针会向右移动一个位置，而右指针会向左移动若干个位置，这个与数组的元素有关，但左右指针一共会移动的位置数为 \(O(N)\) ，均摊下来，每次也向左移动一个位置，因此时间复杂度为 \(O(N)\) 。
需要注意的是要注意去重。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
43public static List<List<Integer>> threeSum(int[] nums) {
if (nums == null || nums.length < 3) {
return new ArrayList<>();
}
List<List<Integer>> ans = new ArrayList<>();
int n = nums.length;
Arrays.sort(nums);
for (int i = 0; i < n - 2; i++) {
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = n - 1;
int target = -nums[i];
while (left < right) {
int sum = nums[left] + nums[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else if (sum == target) {
ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
//
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
}
}
}
return ans;
}
复杂度分析
- 时间复杂度：\(O(N^2)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
- 空间复杂度：\(O(\log N)\)。
这道题我在做的时候，看了解题之后，对sum == target之后，一定要做left++; right--有点不解，不可以只left++或者right--吗？
后来才想到，现在已经是sum == target，如果只处理任何一边，如果还相等的话，那说明得到的还是重复的数据，所以需要两边操作，然后如果还是遇到重复的数字，那还需要继续处理。
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗