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

15题: leetcode.cn/problems/3sum/" rel="nofollow">三数之和

给你一个整数数组 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循环， 则会超时~）

解答:

java">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循环。

如图所示：

在这里插入图片描述

java">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;
    }
}