题目描述
给你一个包含 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]
输出：[]
条件分析
- 一个答案中具有相同值的元素可能出现多次；
- 三元组不能是重复的；
- 不需要考虑元素的下标，只需要返回对应的值即可；
- 核心问题是解决如何判断解是否重复的问题；
解题思路（查找表）
-
先对数组进行排序，这样在求解时，只要解与前一个解相同，则可以判断重复，从而进行跳过；
-
外层定义一个循环i，使用指针碰撞的思路，分别从left和right对数组进行遍历，如果nums[left]+nums{right]=0-nums[i],则说明找到了一个解，left右移，right左移，如果移动后元素没有改变，跳过该元素；
-
使用提前判断的方法来去重和提高效率，如果nums[i]>0或者nums[i+1]=nums[i],则继续进行循环；定义两个临时变量存储上次匹配的结果，将解的范围不断缩小；
编码如下
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length < 3) {
return result;
}
quickSort(nums, 0, nums.length-1);
for (int i = 0; i<=nums.length-3; i++) {
if(nums[i]>0) {
continue;
}
if (i > 0 && nums[i] == nums[i-1]) {
continue;
}
int left = i+1;
int right = nums.length-1;
int resultLeft = -1;
int resultRight = nums.length;
int target = 0-nums[i];
while (left < right) {
if (resultLeft != -1 && nums[left] == nums[resultLeft]) {
left++;
continue;
}
if (resultRight != nums.length && nums[right] == nums[resultRight]) {
right--;
continue;
}
int sum = nums[left] + nums[right];
if (sum > target) {
right--;
} else if (sum == target) {
List<Integer> solution = new ArrayList<>(3);
solution.add(nums[i]);
solution.add(nums[left]);
solution.add(nums[right]);
result.add(solution);
resultLeft = left;
resultRight = right;
left++;
right--;
} else {
left++;
}
}
}
return result;
}
// nums[q,k]存储的是小于指定标定点的元素，nums[k,r]存储的是小于指定标定点的元素
private void quickSort(int[] nums, int p, int r) {
if (p >= r) {
return;
}
int q = partion(nums, p, r);
quickSort(nums, p, q-1);
quickSort(nums, q+1, r);
}
private int partion(int[] nums, int p, int r) {
int pivot = nums[r];
int i = p;
for (int j = p; j<=r-1; j++) {
if (nums[j] < pivot) {
swapInt(nums, j, i);
i++;
}
}
swapInt(nums, i, r);
return i;
}
public void swapInt(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}