LeetCode15.三数之和

题目链接：15. 三数之和 - 力扣（LeetCode）

1.常规解法（会超时）

由于这道题需要排除相同的三元组，则可以先将目标数组从小到大排序，再遍历数组找到每个符合条件的三元组，若结果中不包含该三元组，就将该结果添加到目标结果中，代码如下：

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[k]);
                        if (!ret.contains(list)) {
                            ret.add(list);
                        }
                    }
                }
            }
        }
        return ret;
    }

2. 双指针算法

和常规解法一样，我们要先将目标数组从小到大排序，由于要求三数之和等于0，我们可以先固定一个数，只需找到剩下的哪两个数与这个数的和为0，再定义一个顺序表存放三元组。

定义三个指针left，right，p，先将p固定在最后一个数，left在第一个数的位置，right在倒数第二个数的位置，接下来在每一轮循环中，保持p不动，只要移动left和right即可。

当nums[left] + nums[right] + nums[p] > 0，由单调性知，若保持right不动，left右边的数均大于left指向的数，导致三数之和只会越加越大（数组是从大到小排序的），这时就要将right向左移动一位；当nums[left] + nums[right] + nums[p] < 0，由单调性知，若保持left不动，right左边的数均小于right指向的数，导致三个数之和会越加越小，这是就要将left向右移动一位；当nums[left] + nums[right] + nums[p] == 0，就要将这个结果添加到顺序表中，由于最后的结果不允许出现相同的三元组，这时就要去重。

去重：若使用contains判断三元组是否重复，代码就会超时，这时我们就要在nums[left] + nums[right] + nums[p] == 0时，将与left和right指向的数的相同的数去掉，由于这个数组是有序的，那么相同的数就会聚集在一起，只需要使用while循环去重即可；相同的，当left与right相遇时，第一轮循环结束，也去要进行去重操作，将与p指向的数相同的数跳过即可。

优化：当p指向的元素小于0时，由单调性知，p左边的元素均小于0，就不存在三个数之和为0的情况，直接返回结果即可。

流程图与代码如下：

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        int p = n - 1;
        while (p > 1) {
            int left = 0;
            int right = p - 1;
            if (nums[p] < 0) {
                return ret;
            }
            while (left < right) {
                if (nums[left] + nums[right] + nums[p] < 0) {
                    left++;
                } else if (nums[left] + nums[right] + nums[p] > 0) {
                    right--;
                } else {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[left]);
                    list.add(nums[right]);
                    list.add(nums[p]);
                    ret.add(list);
                    int numLeft = nums[left++];
                    while (nums[left] == numLeft && left < right) {
                        left++;
                    }
                    int numRight = nums[right--];
                    while (nums[right] == numRight && left < right) {
                        right--;
                    }
                }
            }
            int numP = nums[p--];
            while (nums[p] == numP && p > 1) {
                p--;
            }
        }
        return ret;
    }

 希望大家积极指出不足之处