给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0，请你找出所有和为 0 且不重复的三元组
https://leetcode-cn.com/problems/3sum/
示例1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例2：
输入：nums = []
输出：[]
示例3：
输入：nums = [0]
输出：[]
提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
Java解法
思路：
熟悉的遍历算法，条件不一致，取出第一个数，遍历剩下的数中满足b+c=-a- 没那么简单，自己坑了自己，去重是不能去的，应该要先排序的
- 先排序（熟悉了下快排），然后依次遍历数据，注意若数据与前一位相同则需要跳过（排过序所以不用担心需要往前找），中间要记得优化，数据越来越大的，所以相加为0的数据必定是两端往内部收敛
- 存入数据忘记判断条件，导致超时验证，自行运行花了5秒，还是错的，要注意
package sj.shimmer.algorithm;
import java.util.ArrayList;
import java.util.List;
/**
* Created by SJ on 2021/2/3.
*/
class D10 {
public static void main(String[] args) {
System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
System.out.println(threeSum(new int[]{0}));
System.out.println(threeSum(new int[]{0,0,0}));
}
public static List<List<Integer>> threeSum(int[] nums) {
ArrayList<List<Integer>> results = new ArrayList<>();
if (nums == null || nums.length < 3) {
return results;
}
quickSort(nums, 0, nums.length - 1);
Utils.logTime();
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i-1]) {
continue;
}
int k = nums.length-1;
for (int j = i + 1; j < nums.length; j++) {
if (j > i + 1 && nums[j] == nums[j-1]) {
continue;
}
//定了唯一的 i,j 就只有唯一的k
while (j<k&&nums[i] +nums[j] +nums[k]>0){
k--;
}
if (j==k) {
//这一轮再也查不到了
break;
}
if (nums[i] +nums[j] +nums[k]==0) {
List<Integer> integers = new ArrayList<>();
integers.add(nums[i]);
integers.add(nums[j]);
integers.add(nums[k]);
results.add(integers);
}
}
}
return results;
}
private static int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
//找到基准交换后的位置、作为下次分割边界
int spiltIndex = findPonitIndex(arr, left, right);
quickSort(arr, left, spiltIndex - 1);
quickSort(arr, spiltIndex + 1, right);
}
return arr;
}
private static int findPonitIndex(int[] arr, int left, int right) {
int point = arr[left];//以左边界为比较基准值
while (left < right) {
//以左为基准，先从右侧遍历,小于基准交互
while (point <= arr[right] && left < right) {
right--;
}
if (left < right) {
//未相遇, 第一个左侧值是基准，已被记录
arr[left] = arr[right];
}
//左侧遍历,大于基准跳出
while (point > arr[left] && left < right) {
left++;
}
if (left < right) {
//未相遇, 第一个右侧值移至原基准位置，已被记录
arr[right] = arr[left];
}
}
arr[left] = point;
return left;
}
}
image
官方解
-
排序 + 双指针
我参考的就是这种写法，但他们排序用的直接是
Arrays.sort(nums);官方解优化了三重循环的第二次与第三次，因为有序，且结果固定，所以用双指针优化了该嵌套
- 时间复杂度： O(N2)，其中 N 是数组 nums 的长度
- 空间复杂度：O(logN)。忽略存储答案的空间，额外的排序的空间复杂度为O(logN)。然而我们修改了输入的数组 nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序，空间复杂度为 O(N)
