题目

思路

双指针法 + 去重

为啥要去重呢？因为题目中说了要返回不重复的三元组。拿示例1来看，（-1，0，1）和（0，1，-1）虽然都等于0，但其实它们里面的数都是一样的，最后只输出一个即可。

先说双指针法：

变量i用来从左到右遍历数组。然后设置一个left指针和一个right指针，分别指向 nums[i+1]和 nums[nums.length-1]。i的这个循环相当于固定第一个数，找出剩下两个数。

为了方便后续的说明，将i指向的元素称为a,left指向的为b,right指向的为c,我们目标是a+b+c=0

另外在开始前的一个重要的操作是要对数组进行排序（从小到大排序）

• 如果 nums[i]+nums[left]+nums[right] < 0 了，那么我们让left++ ,这是因为我们已经从小到大排好序了，现在sum<0，我们想让sum更大一些， i是固定的了，所以只能让left往左移
• 如果nums[i]+nums[left]+nums[right] > 0 了，我们就让right–，理由类比上面。
• 如果当前nums[i]+nums[left]+nums[right] 正好等于0了，我们将这三个数记录下来。然后left++,right–,寻找下一个三元组。

去重：

分为三部分去重：

a的去重：

• 如果nums[i]==nums[i-1],则我们该找下一个i了。
• 为啥呢？举个例子 -2，-2，0，0，1，1，2，4 当指向第一个-2的时候，我们经过双指针法，已经找到了-2是第一个数的所有等于0的三元组了。这时候我们要进入下一个循环了，i指向了第二个-2,很明显这时候再进行双指针法找到的所有满足sum=0的三元组，都会包含在第一个-2的三元组的结果里。

b和c去重：

• b的去重。nums[left+1]==nums[left]
• c的去重。nums[right-1]==nums[right]

代码

//没有去重

import java.lang.reflect.Array;
import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        //对数组从小到大进行排序
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {

            if (nums[i] > 0)
                break;

            int left = i + 1;
            int right = nums.length - 1;

            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                	right--;
                }
            }
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

//去重


import java.lang.reflect.Array;
import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        //对数组从小到大进行排序
        Arrays.sort(nums);
		
        for (int i = 0; i < nums.length; i++) {
			//如果a就大于0了，后面的数都大于等于a，肯定sum不等于0
            if (nums[i] > 0)
                break;
            //对a去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;

            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    //对b和c去重
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    //找到一个三元组后，继续寻找下一个三元组
                    left++;
                    right--;
                }

            }
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)