给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
第一种思路：
利用到二分搜索的思想，难点是在于去掉重复选取的问题，
- 首先将数组排序
Arrays.sort(nums)。 - 循环遍历排序后的数组，选取第一个元素用
i表示下标。
1). 对第一个元素进行检查，如果nums[i]大于0，则结束循环。因为数组已经有序了，i后面的元素也都全大于0。if(nums[i] > 0) break;
2). 从i + 1开始循环选取第二个元素，用j表示第二个元素下标。
a. 然后利用二分搜索的思想在j + 1到nums.length之间寻找第三个元素。
b. 对第二个元素去重，在第二层循环中，每次选取第三个元素后，都要对第二个元素j检查是否有重复的元素，跳过重复的元素。while(j < nums.length-1 && nums[j] == nums[j+1]) j++;
3). 第二层循环结束后， 对第一个元素去重。while(i < nums.length-1 && nums[i] == nums[i+1]) i++;
class Solution {
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> allSum = new ArrayList<>();
// 排序
Arrays.sort(nums);
int num;
int index; // 第三个元素的下标。
for (int i = 0; i < nums.length - 1; i ++){
if(nums[i] > 0) // 右边大于0，后面的无解
break;
for(int j = i+1; j < nums.length - 1; j ++){
// 前两个元素的和
num = nums[i] + nums[j];
// 利用到二分搜索查找第三个元素。
index = Arrays.binarySearch(nums, j+1, nums.length, -num);
// 找到元素的情况
if (index >= 0){
List<Integer> sum = new ArrayList<>(3);
sum.add(nums[i]);
sum.add(nums[j]);
sum.add(nums[index]);
allSum.add(sum);
}
// 第二个元素去重
while(j < nums.length-1 && nums[j] == nums[j+1])
j++;
}
// 第一个元素去重
while(i < nums.length-1 && nums[i] == nums[i+1])
i++;
}
return allSum;
}
}
执行结果：通过显示详情
执行用时 :108 ms, 在所有 Java 提交中击败了14.92%的用户。
内存消耗 :45.3 M, 在所有 Java 提交中击败了96.53%的用户。
第一种方法消耗的时间太长了。然后查看了评论区发现了第二种思路。
第二种思路：
使用双指针在数组中动态选取元素。
- 对数组进行排序，
Arrays.sort(nums)。 - 循环遍历数组，选取第一个元素用
i表示其下标。
1). 对第一个元素进行检查，如果nums[i]大于0，则结束循环 。
2). 用左指针 left 选取第二个元素left = i + 1，右指针 right 选取第三个元素right = nums.length - 1。
3). 当 left < right 时，执行第二层循环遍历数组。
a. 当 nums[i] + nums[left] + nums[right] == 0 时，说明找到了解，保存元素，同时需要检查左右指针指向的元素是否与下一个解相同，去掉重复的解，移动左右指针left ++,right--，寻找下一个解。
b. 当 nums[left] + nums[right] ＜ 0 - nums[0]，此时 nums[left] 的值偏小，移动左指针 left++。
c. 当 nums[left] + nums[right] > 0 - nums[0], 此时 nums[right] 的值偏大，移动右指针right --;
4). 结束第二层循环后，同样需要对第一个元素 i 进行去重操作。
class Solution {
public static List<List<Integer>> threeSum(int[] nums){
List<List<Integer>> allSum = new ArrayList<>();
// 排序
Arrays.sort(nums);
for(int i = 0; i < nums.length - 2; i++){
if(nums[i] > 0) // nums[i] 等于0，后面的也就全部大于0;
break;
int left = i + 1, right = nums.length - 1;
int sum = 0 - nums[i];
while(left < right){
if(nums[left] + nums[right] == sum){
allSum.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 去重
while(left < right && nums[left] == nums [left+1]) left ++;
// 去重
while(left < right && nums[right] == nums[right-1]) right --;
left ++;
right --;
}else if(nums[left] + nums[right] < sum){
left ++;
}else{
right --;
}
}
// 去重
while( i < nums.length - 2 && nums[i] == nums[i+1])
i ++;
}
return allSum;
}
}
