【力扣: 15题: 三数之和】

15题: 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意: 答案中不可以包含重复的三元组。

【思路1】

首先对数组进行排序题目等效于： 求 X + Y + Z = 0 ， X ！= Y  ！= Z 而且数组中元素又不可以重复， 那么我们可以认为 三个元素的大小顺序 就是  X <= Y <= Z 那么可以理解 ， X 就是3个元素中，最小的， 如果存在，则一定满足
X <= 0 , 且 Z >= 0 并且当 X= 0 ， 那么一定是 Y=0，且 Z=0 这一种情况。那么可以根据 X+Y 的值 去Z中找 Z = -（X+Y）在第2层for循环中，利用二分查找，进行优化，而不是开启第三层for循环。（如果第三层直接 for循环， 则会超时~）

解答:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;/*** 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请* <p>* 你返回所有和为 0 且不重复的三元组。*/
public class Solution {// 第3层循环改为2分查找public List<List<Integer>> threeSum(int[] nums) {// 默认 x , y, z 由小到大List<List<Integer>> list = new ArrayList<>();// 1. 对数组进行排序Arrays.sort(nums);// 2. 进行遍历for (int i = 0; i < nums.length; i++) {// 如果x>0,则直接结束for循环if (nums[i] > 0) {break;}if (i >= 1 && nums[i] == nums[i - 1]) {continue;}for (int j = i + 1; j < nums.length; j++) {if (j >= 2 && (j - 1 > i) && nums[j] == nums[j - 1]) {continue;}// 用二分查找, 查找是否存在 值为  -(nums[i]+nums[j]) 的值// 初始下标 k=j+1 , 终止下标: k=nums.length-1 , 且有序int start = j+1 ;int end = nums.length-1;int index = twoSplitSearch(nums, start, end, -(nums[i] + nums[j]));if (index<0){continue;}List<Integer> integers = Arrays.asList(nums[i], nums[j], nums[index]);list.add(integers);}}return list;}// 二分查找public static int twoSplitSearch(int[] ints,int startIndex, int endIndex,int target ){int result = -1;if (startIndex>endIndex){return result;}int mid = (startIndex+endIndex)/2;while (ints[mid]!=target && startIndex<endIndex){if (target > ints[mid]){startIndex=mid+1;}else {endIndex=mid-1;}mid=(startIndex+ endIndex)/2;}if (ints[mid]==target && mid>=startIndex){result=mid;}return result;}
}

自己记录这个解法也只是刚刚通过, 还是很慢, 后面再更新更好的解法。

------------------ 更新-------------------------2024-07-07 --------------------------

【思路3】

同样借助上面思路1的思想， 如果我们对仅仅根据 X 去找另外的2个值  Y， Z， 那样就只要一个for循环，利用双指针的思想。同样，当 X > 0 即可结束最外层的for循环。如图所示：

在这里插入图片描述

public class Solution {public static void main(String[] args) {Solution solution = new Solution();List<List<Integer>> list = solution.threeSum(new int[]{-4, -2, -2, -2, 0, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6});System.out.println(list);}// 时间复杂度是 o(n^2)public List<List<Integer>> threeSum(int[] nums) {// 默认 x , y, z 由小到大List<List<Integer>> list = new ArrayList<>();// 1. 对数组进行排序Arrays.sort(nums);// 2. 进行遍历for (int i = 0; i < nums.length; i++) {// 如果x>0,则直接结束for循环if (nums[i] > 0) {break;}if (i >= 1 && nums[i] == nums[i - 1]) {continue;}int left = i + 1;int right = nums.length - 1;while (left < right) {int total = nums[left] + nums[right];// 去重判断if (left - 1 > i && nums[left - 1] == nums[left]) {left++;continue;}// 去重判断if (right < nums.length - 1 && nums[right] == nums[right + 1]) {right--;continue;}if (total == -nums[i]) {// 采集结果List<Integer> result = new ArrayList<>();result.add(nums[i]);result.add(nums[left]);result.add(nums[right]);list.add(result);// 那下一步到底是移动左还是右呢?// 尝试左移?// 尝试右移?// 直接左移有指针, 或者右移左指针都可以
//                    left++;right--;} else if (total > -nums[i]) {right--;} else {left++;}}}return list;}
}