题目:三数之和
给你一个包含n
个整数的数组nums
,判断nums
中是否存在三个元素a,b,c
,使得a + b + c = 0
?请你找出所有和为0
且不重复的三元组。
注意:答案中不可以包含重复的三元组。
- 示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
- 示例 2:
输入:nums = []
输出:[]
- 示例 3:
输入:nums = [0]
输出:[]
- 提示:
0 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5
思路1
先固定一个数i
,然后对另外两个数使用双指针,找到两个数之和等于-nums[i]
。
定义一个HashSet
,把结果三元组存放进HashSet
中来去重,最后再把HashSet
转化为ArrayList
,返回一个ArrayList
。
- 时间复杂度:O(n²)
- 空间复杂度:O(n)
代码
public List<List<Integer>> threeSum(int[] nums) { // 总时间复杂度:O(n²)
// 用set存,可以去重
Set<List<Integer>> set = new HashSet<>(); // 空间复杂度:O(n)
Arrays.sort(nums); // 时间复杂度O(nlog₂n)
for (int i = 0; i < nums.length; i++) { // 时间复杂度O(n²)
int left = i + 1;
int right = nums.length - 1;
int target = -nums[i];
while (left < right) { // 时间复杂度O(n)
int sum = nums[left] + nums[right];
if (sum == target) {
set.add(Arrays.asList(nums[i], nums[left], nums[right]));
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return new ArrayList<>(set); // 空间复杂度:O(n)
}
思路2
先固定一个数i
,然后对另外两个数使用双指针,找到两个数之和等于-nums[i]
。
再手动去重,把结果三元组存放进ArrayList
,返回ArrayList
,可以使空间复杂度降到O(n)。
- 时间复杂度:O(n²)
- 空间复杂度:O(n)
代码
public List<List<Integer>> threeSum(int[] nums) { // 总时间复杂度O(n²)
if (nums == null || nums.length < 3) {
return new ArrayList<>();
}
List<List<Integer>> list = new ArrayList<>(); // 空间复杂度:O(n)
Arrays.sort(nums); // 时间复杂度O(nlog₂n)
for (int i = 0; i < nums.length; i++) { // 时间复杂度O(n²)
if (nums[i] > 0) {
break; // 第一个数大于 0,后面的数都比它大,肯定不成立了
}
// 去掉重复情况
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
int target = -nums[i];
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
list.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 现在要增加 left,减小 right,但是不能重复
// 当左右指针扫描到与上一个相等的时候,直接跳过
while (left < right && nums[left] == nums[++left]) {
}
while (left < right && nums[right] == nums[--right]) {
}
} else if (sum < target) {
// 当左指针扫描到与上一个相等的时候,直接跳过
while (left < right && nums[left] == nums[++left]) {
}
} else {
// 当右指针扫描到与上一个相等的时候,直接跳过
while (left < right && nums[right] == nums[--right]) {
}
}
}
}
return list;
}