三数之和

15. 三数之和

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

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

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

题目中要找到所有「不重复」且和为 0 的三元组，这个「不重复」的要求使我们不能简单地使用三重循环枚举所有三元组。如果直接使用三重循环枚举三元组，会得到O(n^3) 个满足题目要求的三元组，时间复杂度至少为 O(n^3)。在这之后还需要进行去重操作，时间复杂度和空间复杂度都很高。

我们先将数组进行排序枚举三元组(a, b, c) 满足 a <= b <= c，这样排除了(b, c, a)等情况。同时对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复。

[0, 1, 2, 2, 3]
 ^  ^  ^

三重循环第一次枚举到的三元组为 (0, 1, 2)，如果第三重循环继续枚举下一个元素，则会造成重复。因此我们需要将第三重循环跳到下一个不相同的元素。

对于第二三重循环，我们可以使用双指针来降低复杂度，当第一层循环遍历到数字 a 时，就变为求 nums 中 a 后的有序子数组中两数之和为 -a，可以使用双指针来找出这两个数。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();

        //枚举 a
        for(int a = 0; a < n; a++){
            //需要和上一次枚举的数不相同
            if(a > 0 && nums[a] == nums[a - 1]){
                continue;
            }

            // c 对应的指针初始指向数组的最右端
            int c = n - 1;
            int target = -nums[a];
            //枚举 b
            for(int b = a + 1; b < n; ++b){
                //需要和上一次枚举的数不相同,a 和 b 都不同，结果组合一定不会相同
                if(b > a + 1 && nums[b] == nums[b - 1]){
                    continue;
                }
                // b 的指针在 c 指针左侧
                while(b < c && nums[b] + nums[c] > target){
                    --c;
                }

                //指针重合，随着 b 的增加就不会有满足 a+b+c=0 且 满足 b<c 的 c 了，退出循环
                if(b == c){
                    break;
                }

                if(nums[b] + nums[c] == target){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[a]);
                    list.add(nums[b]);
                    list.add(nums[c]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }
}

时间复杂度 O(n^2)，空间复杂度O(logN)，这里忽略了存储答案的空间。