题目：15. 三数之和
如果您已经有思路了，或者是N刷了，可以先自己写一遍。
题目分析
题目说明：给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意，与两数之和不同，这里返回的是元素，不是下标。
解题思路
这个问题可以通过使用排序和双指针技术来解决。为了避免重复的三元组，首先应该对数组进行排序，然后通过两头夹逼法，找出所有可能的两个数和当前元素相加结果为0。
最重要的：题目中并没有规定不能有重复元素，为了避免添加重复的三元组，我们需要跳过数组中重复的元素。
具体步骤如下：
- 排序：首先，将数组排序。这是解决问题的前提，因为排序后可以使用双指针技术，并且更容易避免重复的三元组。
- 遍历：然后，遍历排序后的数组，对于每个元素，使用双指针找出所有可能的两个加数，使它们的和加上当前元素的值为0。
- 两头夹逼法：对于每个元素，我们在其之后的元素中设置左右指针，分别指向紧挨着这个元素的下一个元素和数组的最后一个元素。如果当前指针元素之和小于0，则移动左指针以增加总和；如果总和大于0，则移动右指针以减少总和。
- 避免重复：跳过重复的元素，以避免重复的三元组。
解题关键：排序 + 两头夹逼法 + 跳过重复元素
Java解法
下面是使用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
| import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length && nums[i] <= 0; ++i) {
if (i == 0 || nums[i - 1] != nums[i]) {
resolve(nums, i, result);
}
}
return result;
}
void resolve(int[] nums, int i, List<List<Integer>> result) {
int lo = i + 1, hi = nums.length - 1;
while (lo < hi) {
int sum = nums[i] + nums[lo] + nums[hi];
if (sum < 0) {
++lo;
} else if (sum > 0) {
--hi;
} else {
result.add(Arrays.asList(nums[i], nums[lo++], nums[hi--]));
while (lo < hi && nums[lo] == nums[lo - 1])
++lo;
}
}
}
}
|
解法的时间复杂度主要由排序决定，排序的时间复杂度为 O(nlogn)，遍历数组和双指针搜索的时间复杂度为 O(n^2)。因此，总的时间复杂度为 O(n^2)。
References
