[Java·算法·中等] LeetCode15. 三数之和

题目

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

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

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

示例

示例1

输入：nums = [-1,0,1,2,-1,-4]

输出：[[-1,-1,2],[-1,0,1]]

解释：

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。

nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。

nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。

不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。

注意，输出的顺序和三元组的顺序并不重要。

示例2

输入：nums = [0,1,1]

输出：[]

解释：唯一可能的三元组和不为 0 。

示例3

输入：nums = [0,0,0]

输出：[[0,0,0]]

解释：唯一可能的三元组和为 0

提示

👉️ 力扣原文

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(int k=0;k<nums.length - 2;k++){
            if(nums[k] > 0) break;
            if(k>0 && nums[k] == nums[k-1]) continue;
            int i=k+1,j=nums.length - 1;
            while(i < j){
                int sum = nums[k] + nums[i] +nums[j];
                if(sum < 0){
                    while(i<j && nums[i] == nums[++i]);
                }else if(sum>0){
                    while(i < j && nums[j] == nums[--j]);
                }else{
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[k],nums[i],nums[j])));
                    while(i < j && nums[i] == nums[++i]);
                    while(i < j && nums[j] == nums[--j]);
                }
            }
        }
        return res;
    }
}

详细解读

让我解释一下代码的主要逻辑：

1. 首先，对给定的整数数组进行排序，这是为了方便后续的处理，使得相同元素在一起，并且方便进行指针移动来遍历可能的三元组。
2. 然后，使用三个指针，其中一个指向当前处理的元素（k），另外两个分别指向当前元素的下一个（i）和数组末尾（j）。
3. 在循环中，首先判断当前元素是否大于零，若是，则直接跳出循环，因为后面的元素都是正数，无法组成三元组使得和为零。
4. 如果当前元素不是第一个元素，并且与前一个元素相同，则跳过该元素，以避免重复计算。
5. 然后，在内部的 while 循环中，通过不断移动 i 和 j 指针，逐步向中间靠拢，同时判断三个元素之和与零的关系：

1. 若和小于零，则移动 i 指针直到找到一个不同的值；
2. 若和大于零，则移动 j 指针直到找到一个不同的值；
3. 若和等于零，则将这个三元组加入结果集中，并继续移动 i 和 j 指针直到找到不同的值。

6. 最后，返回结果集。

这段代码的时间复杂度为 O(n^2)，其中 n 是数组的长度。因为在循环中，i 和 j 指针分别最多遍历一次整个数组。