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;}

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