[Leetcode][15. 三数之和] 3种方法:暴力,Hash,双指针

By Long Luo

Leetcode 15. 三数之和 题解。

方法一:暴力遍历

思路与算法:

首先想到的是暴力枚举\(3\)层循环,但结果肯定会出现重复的数字,我们可以使用HashSet来去除重复元素。

值得注意的是需要先进行排序,如果不排序的话,会返回重复的答案,因为虽然List元素都相同,但顺序不同,还是重复的三元组。

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public 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
36
public 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(logN)\),额外的排序的空间复杂度为\(O(logN)\)

方法二: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
30
public 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
43
public 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. 😉😃💗