这是我参与更文挑战的第12天，活动详情查看： 更文挑战

前言

力扣第十五题 三数之和 如下所示：

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

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

示例 1：

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

示例 2：

输入：nums = []
输出：[]

示例 3：

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

一、思路

要注意题目的结果时需要 不重复的所有解，即数学中的组合排列 C(N,3） 。

这一题最简单的方法使用 三重循环 找出所有的排列，然后看每一组值是不是相加为0。比如示例1 中的 [-1,0,1,2,-1,-4] 就会有 6X5X4 种排列可能，这种方法的时间复杂度太高了，所有需要舍弃。

那么问题来了，怎么优化呢？

tips：下面分析以示例1中国的 nums = [-1,0,1,2,-1,-4] 作为例子来分析

不妨让数组 nums 以升序排列，结果为 nums = [-4,-1,-1,0,1,2,]。当我们从左边选择了两个元素后如 -4, -1，你会发现即使我们拿到最左边的最大值 2 来做匹配都是小于0（ (-4) + (-1) + 2 < 0 ）的，说明 -4, -1无论加上哪一个元素都不会出现0，你就可以直接跳过当前的循环，以减少时间复杂度。

综上所述，思路分为以下两步

• 将nums升序排列
• 选择前两个元素从左边开始，第三个元素从右边开始

二、实现

具体实现时需要注意以下一点

• 如果出现相同元素需跳过当前循环，继续下一次。如 [-2, -1, -1 , 0, 1] ，在已经得到 -1, 0, 1这组结果后，会再次碰到以 -1 作为第一个元素，此时需要跳过

代码实现

代码中注释还是比较完整的，与思路保持一致。

变量说明
ret：结果集

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        // 特殊情况
        if (nums == null || nums.length < 3)
            return ret;
        // 先将数组变为升序的
        Arrays.sort(nums);
        // 复杂度O(n^2)
        for (int i=0; i<nums.length-2; i++) {
            // 如果第一个元素和前一个元素相同的话可以跳过
            if (i != 0 && nums[i] == nums[i-1])
                continue;
            // 第三重循环对应的指针，从最右边开始
            int m = nums.length-1;
            for (int j=i+1; j<nums.length-1; j++) {
                // 如果第二个元素和前一个元素相同的话可以跳过
                if (j != i+1 && nums[j] == nums[j-1])
                    continue;
                // 向左移动指针，且右指针在左指针的右边
                while(j < m && nums[i]+nums[j]+nums[m]>0) {
                    m = m-1;
                }
                // 如果最右边的值都不能满足，则跳出当前循环
                if (j == m) {
                    break;
                }
                if (nums[i] + nums[j] + nums[m] == 0) {
                    ret.add(Arrays.asList(nums[i], nums[j], nums[m]));
                }
            }
        }
        return ret;
    }
复制代码

测试代码

    public static void main(String[] args) {
        int [] nums = {0,1,1};
        new Number15().threeSum(nums);
    }
复制代码

结果

三、总结

感谢看到最后，非常荣幸能够帮助到你~♥