leetcode 15 - 三数之和

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum

给你一个包含 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]
输出：[]
 
提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105

题解：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {// 总时间复杂度：O(n^2)
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length <= 2) return ans;

        Arrays.sort(nums); // O(nlogn)

        for (int i = 0; i < nums.length - 2; i++) { // O(n^2)
            if (nums[i] > 0) break; // 第一个数大于 0，后面的数都比它大，肯定不成立了
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 去掉重复情况
            int target = -nums[i];
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] == target) {
                    ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
                    
                    // 现在要增加 left，减小 right，但是不能重复，比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3
                    left++; right--; // 首先无论如何先要进行加减操作
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (nums[left] + nums[right] < target) {
                    left++;
                } else {  // nums[left] + nums[right] > target
                    right--;
                }
            }
        }
        return ans;
    }
}

思路：

• 首先我们需要认真的审题，题目中有两个条件：1.找出三个和为0的数； 2.不能重复，所以围绕着这两个条件，我们来找解决方法

• 最简单直接能想出的方法就是直接来个三重循环，但是这样无疑是最暴力直接也是比较笨的方法，但是如果简单的三重循环还是无法保证不重复这个问题，如果想要不重复，那么首先进行排序是最好的办法，例如一组排序号的数字[0, 1, 2, 2, 2, 3]，数字是有重复的情况，排序好之后再进行三重循环，举个例子：如果简单的想要找到和为3的数组，那么就有 0，1，2 然后三重遍历肯定就会找到三组0，1，2，无法保证重复，所以在遍历的过程中我们还得保证各个相邻循环的数字不能相同，例如第一次找到0，1，2 ，第三重循环下一次就得跳过2，到3.

• 和为0的逻辑我们打算用三重循环，不重复我们也有了逻辑，那么这个三重循环是否可以优化呢？可以的，我们想下，第一个数字确定的情况下，我们寻找第二个和第三个数字，假如第一个数字为a，第二个第三个分别为b，c ,存在情况a+b+c=0,已知a的情况下，如果第二个循环继续遍历下一个数字b'，我们是知道b'大于b的，那么如果存在c'保证 a+b'+c'=0,是不是c'<c的？我们可以好好想想：a+b+c=0 如果b的值大了，那么如果要保证等式成立，是不是c必然得小一点才行，这么理解是不是简单多了，由此呢，我们就可以优化这个三重循环了。

• 第一重循环不变，接下来我们使用一重循环即可，b从去掉a左边的剩余的数组的左边开始，c从右边开始，b和c都向着互相的方向行进即可。

• 回到上述的代码中，首先我们得过滤掉数组个数为0，或者2的，然后进行排序

• 下面这个代码，作者已经给出注释了，意思就是我们以第一重循环的数字为准，来找后面两个数字，如果第一重循环确定的数字都大于0，那就不用想，经过排序的数组，后面的数字必然大于0，就无法确保三个数和为0了。

if (nums[i] > 0) break; // 第一个数大于 0，后面的数都比它大，肯定不成立了

• 下面的代码就是确保第一重循环的数字，与第二重数字一致的，去掉，保证不重复

if (i > 0 && nums[i] == nums[i - 1]) continue; // 去掉重复情况

• 接下来都比较简单，我们可以多理解理解原理就理解了。