15. 三数之和

给你一个整数数组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 。

提示：

$3 \leq n u m s . l e n g t h \leq 3000$
$- 10^{5} \leq n u m s [i] \leq 10^{5}$

解法一(排序+双指针)

思路分析

首先思考暴力求解，其时间复杂度为 $O (n^{3})$ ，同时还需要使用哈希表对所得元组进行去重，对此需要换一种思路来解决。
我们需要思考不重复的本质，对于一个三元组[1, 2, 3]，有六种排列情况，为了避免出现六种情况，可以对三个元素进行保证，即
1. 第二个元素不低于第一个元素
2. 第三个元素不低于第一个元素
即保证三元组[a, b, c]，满足 $a \leq b \leq c$ ，如此在枚举三个元素时，可以保证不会出现重复的元组，即因为 $a \leq b \leq c$ ，不会出现枚举出[2, 3, 1]的情况，即只会出现[1, 2, 3]的情况
因此我们可以对题目给出数组 nums进行排序，然后再去寻找满足条件的三元组，如此可避免重复情况，也方便排除重复的三元组
因为需要寻找满足 $a + b + c = 0$ 的三元组，因此对于暴力求解中的第二重循环和第三重循环，可以发现每当b从前往后枚举增加时，c应该减少才能继续满足a+b+c = 0的关系式
因此我们可以使用双指针，即当需要枚举数组的两个元素时，发现伴随第一个元素的递增，第二个元素是递减的，那么可以使用双指针(相向双指针)，将枚举的时间复杂度由 $O (n^{2})$ 减少至 $O (n)$
所以我们可以使用双指针来寻找b和c，同时需要注意的是，需要一直保持左指针小于右指针，即保证 $b \leq c$ ，且当a+b+c > 0时，说明c的值过大，右指针需要向做移动，当a+b+c < 0时，说明b的值较小，左指针需要向右移动；当找到对应元组，即a+b+c = 0时，将元组保存到返回结果中，并移动左右指针
同时因为数组中会出现重复元素，即排序后这些重复元素会排列在一起，因此我们进行去重操作，如if(i>0 && nums[i] == nums[i-1]) continue

实现代码

java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);    // 对数组元素进行排序
        for (int i = 0; i < nums.length-2; ++i) {    // 寻找元组的第一个数a
            if (i > 0 && nums[i] == nums[i-1]) {    // 跳过重复的数
                continue;
            }
            int a = nums[i];    // 找到元组的第一个数a
            // 寻找元组的第二个数b和第三个数c
            int j = i+1;
            int k = nums.length-1;
            while (j < k) {        // 相向双指针 遍历寻找
                int s = a + nums[j] + nums[k];
                if (s > 0) {    // 说明 c 的值过大
                    -- k;        // 移动右指针 往前继续寻找 c 即让c减小
                } else if (s < 0) {
                    ++ j;        // 移动左指针 往后继续寻找 b
                } else {    // 找到符合条件的元组
                    List<Integer> list = new ArrayList<>();
                    list.add(a);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    ans.add(list);    // 将元组保存到返回值中
                    // 移动左指针
                    ++ j;
                    while (j < k && nums[j] == nums[j-1])    // 跳过重复的数 避免重复添加相同的元组
                        ++ j;
                    // 移动右指针
                    -- k;
                    while (j < k && nums[k] == nums[k+1])    // 跳过重复的数 避免重复添加相同元组
                        -- k;
                }
            }
        }
        return ans;
    }
}

运行结果

解答成功:
执行耗时:29 ms,击败了87.06% 的Java用户
内存消耗:50.4 MB,击败了16.79% 的Java用户

复杂度分析

时间复杂度： $O (n^{2})$ ，对数组进行排序的时间复杂度为 $O (n l o g^{n})$ ，对数组进行遍历寻找元素的时间复杂度为 $O (n^{2})$ ，综合起来时间复杂度为 $O (n^{2})$
空间复杂度： $O (1)$ ，忽略排序所需要的空间，其余变量只使用了 $O (1)$ 的空间复杂度。

优化解法一(剪枝)

思路分析

在将数组按照非递减顺序排序后，不难确定，当确定一个数a时
若 $a + n u m s [i + 1] + n u m s [i + 2] > 0$ 时，即a与右边相近的连续两个数相加结果大于0，那么a继续与后续的其他数相加，也一定大于0，所以此时已不存在满足 a + b + c = 0的元组，那么可以直接break退出循环。
同时若有 $a + n u m s [n - 2] + n u m s [n - 1] < 0$ ，即此时的a与数组中两个最大的元素相加结果依然小于0，那么a与其他数组元素相加的结果依然会小于0，也不存在满足a + b + c = 0的元组，所以continue继续往后遍历寻找a

实现代码

java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);    // 对数组元素进行排序
        for (int i = 0; i < nums.length-2; ++i) {    // 寻找元组的第一个数a
            if (i > 0 && nums[i] == nums[i-1]) {    // 跳过重复的数
                continue;
            }
            int a = nums[i];    // 找到元组的第一个数a

            if (a + nums[i+1] + nums[i+2] > 0)    // 因为数组按非递减排序
                break;    // 若此时数组中连续三个数相加结果大于0 则后续不存在别的数使得a+b+c=0成立
            if (a + nums[nums.length-2] + nums[nums.length-1] < 0)
                continue;    // 若此时a+数组中末尾两个最大的数结果小于0 则此时的a添加其他数依然会小于0

            // 寻找元组的第二个数b和第三个数c
            int j = i+1;
            int k = nums.length-1;
            while (j < k) {        // 相向双指针 遍历寻找
                int s = a + nums[j] + nums[k];
                if (s > 0) {    // 说明 c 的值过大
                    -- k;        // 移动右指针 往前继续寻找 c 即让c减小
                } else if (s < 0) {
                    ++ j;        // 移动左指针 往后继续寻找 b
                } else {    // 找到符合条件的元组
                    List<Integer> list = new ArrayList<>();
                    list.add(a);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    ans.add(list);    // 将元组保存到返回值中
                    // 移动左指针
                    ++ j;
                    while (j < k && nums[j] == nums[j-1])    // 跳过重复的数 避免重复添加相同的元组
                        ++ j;
                    // 移动右指针
                    -- k;
                    while (j < k && nums[k] == nums[k+1])    // 跳过重复的数 避免重复添加相同元组
                        -- k;
                }
            }
        }
        return ans;
    }
}

运行结果

解答成功:

执行耗时:25 ms,击败了99.46% 的Java用户

内存消耗:50.1 MB,击败了38.47% 的Java用户

复杂度分析

时间复杂度： $O (n^{2})$
空间复杂度： $O (1)$

注意

对于去重的代码，应该放在最后的添加到结果中，而不是移动左右指针便立马去重，考虑特殊情况，即数组为[0, 0, 0, 0, 0]时

15. 三数之和 ​

解法一(排序+双指针) ​

思路分析 ​

实现代码 ​

运行结果 ​

复杂度分析 ​

优化解法一(剪枝) ​

思路分析 ​

实现代码 ​

运行结果 ​

复杂度分析 ​

注意 ​

15. 三数之和

解法一(排序+双指针)

思路分析

实现代码

运行结果

复杂度分析

优化解法一(剪枝)

思路分析

实现代码

运行结果

复杂度分析

注意