三数之和

题目链接:https://leetcode.cn/problems/3sum/description/

小回说过，未来这个词听上去就是美好，可是你别忘了呀，每一个我们所期待的美好未来，都必须有一个努力的现在。两数之和已经搞定了，那三数之和也不在话下，今天就让我们继续来刷 ECODE

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

示例

java

示例 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。

题目解析

这道题我们可以套用两数之和的思路，先固定一个数，然后去找另外两个数，这样我们就可以转化为两数之和的问题，然后使用双指针来帮助我们解决问题

排序数组：首先我们先对数组进行一个排序，它能让我们应用双指针来避免不必要的重复检查，并且帮助我们更快的缩小范围
固定一个数：在一个 for 循环中，我们先固定一个数，然后剩下的数我们在 while 循环中进行双指针查找
条件判断：我们来想想以下的场景，
1. 要是数组里面的元素都没有三个，我们就直接结束返回空集合；
2. 如果我们在 for 循环里面固定的那个数已经是大于 0 的了，由于我们是经过排序了的，那么剩下的所有数字我们都是大于 0 的了，此时也没有必要进行后面的逻辑了（因为这样就不存在三数之和为 0 了，例如[1,2,3,4,5]），直接结束循环
3. 如果这个数和上面的拿一个数字相等，我们是不是也没有必要进行判断了呢，例如：[-1,-1,-1,0,2]，当我们从第一个 -1 开始逻辑处理的时候我们可以得到一个满足要求的结果[-1,-1,2],其中的两个 -1 分别是第一个和第二个；当我们从第二个 -1 开始判断的话，我们是不是也会得到一个满足题目要求的结果[-1,-1,2],其中的 -1 分别是第二个和第三个。那么就会固定第一个 -1 得到的结果相同，所以我们这里遇到和前者相同的数字我们就进行一个跳过，避免出现重复结果
4. 使用双指针，left 和 right，left 指向我们固定数字的第一个数，right 指向我们数组里面的最后一个数，然后让 left 和 right 分别往中间靠拢来寻找我们需要的数

题目解答

Java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //初始化一个空集合
        List<List<Integer>> result = new ArrayList<>();
        //先判断 nums 数组里面有没有三个元素
        if (nums.length < 3) {
            return result;
        }
        //对 nums 数组进行遍历，使之从小到大的排序
        Arrays.sort(nums);
        //开始进行遍历
        for (int i = 0; i < nums.length; i++) {
            //判断：如果第一个元素的内容都大于 0 了，那么后面的元素都是大于 0 的，不可能出现三数之和还是为 0 的情况
            if (nums[i] > 0) {
                break;
            }
            //去重，如果当前元素和上一个元素相同的话，那么得到的结果将会和上一次有相同的部分，如下
            //所以如果当前元素和上一个元素相同的话，就跳过当前元素
            //-2 -2 -1 2 3 4
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //定义两个指针分别指向 i 的后面一个元素和数组的最后一个元素，从而形成两边往中间靠拢的局势
            int l = i + 1;
            int r = nums.length - 1;
            while (l < r) {
                //判断三数之和能否为 0
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    //进行去重，看 l 右面的元素和 r 左面的元素相同不，相同就跳过该元素
                    //l<r 的这个条件记得带上
                    while (l < r && nums[l] == nums[l + 1]) {
                        l++;
                    }
                    while (l < r && nums[r] == nums[r - 1]) {
                        r--;
                    }
                    l++;
                    r--;
                } else {
                    //判断结果不等于 0 的情况，如果大于 0，右指针往前移动
                    if (sum > 0) {
                        r--;
                    }
                    //如果结果小于 0，那么左指针往后面移动
                    if (sum < 0) {
                        l++;
                    }
                }
            }
        }
        return result;
    }
}

第一次循环

第二次循环

由于第二个 -2 和第一个 -2 一样，我们跳过本次判断，因为这样得到的一个[-2,-1,3]和第一次的一个结果集重复

第三次循环

后面的循环，数都大于 0，结束判断

所以最后我们的结果就是此时 left 和 right 重合了，结束 while 循环，以 i=-2 的第一个数能满足三数之和的结果集就有

[-2,-2,4],[-2,-1,3]

三数之和 ​

题目描述 ​

示例 ​

题目解析 ​

题目解答 ​

三数之和

题目描述

示例

题目解析

题目解答