12. 三数之和

题目：

给你一个包含 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

方法：排序+双指针

题目中要求找到所有「不重复」且和为 00 的三元组，这个「不重复」的要求使得我们无法简单地使用三重循环枚举所有的三元组。这是因为在最坏的情况下，数组中的元素全部为 0，即

[0, 0, 0, 0, 0, 0, 0, 0, ..., 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

任意一个三元组的和都为 0。如果我们直接使用三重循环枚举三元组，会得到 个满足题目要求的三元组（其中 NN 是数组的长度）时间复杂度至少为 。在这之后，我们还需要使用哈希表进行去重操作，得到不包含重复三元组的最终答案，又消耗了大量的空间。这个做法的时间复杂度和空间复杂度都很高，因此需要换一种思路来考虑这个问题。

可以发现，如果我们固定了前两重循环枚举到的元素 a 和 b，那么只有唯一的 cc满足 a+b+c=0。当第二重循环往后枚举一个元素 b’ 时，由于 b’ > b，那么满足 a+b’+c’=0 的 c’ 一定有 c’ < c，即 c’ 在数组中一定出现在 c 的左侧。也就是说，我们可以从小到大枚举 b，同时从大到小枚举 c，即第二重循环和第三重循环实际上是并列的关系。
从这个角度分析，可以保持第二重循环不变，而将第三重循环变成一个从数组最右端开始向左移动的指针。

这个方法就是我们常说的「双指针」，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从 减少至。为什么是呢？这是因为在枚举的过程每一步中，「左指针」会向右移动一个位置（也就是题目中的 b），而「右指针」会向左移动若干个位置，这个与数组的元素有关，但我们知道它一共会移动的位置数为 ，均摊下来，每次也向左移动一个位置，因此时间复杂度为 。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {     
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if(len < 3 || nums == null) return ans;
        //排序
        Arrays.sort(nums);
        for(int i = 0; i < len; i++){
            //排序后的数组若第一个元素大于0，后续三数之和一定大于0，因此直接结束循环
            if(nums[i] > 0) break;
            //去重
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int left = i + 1, right = len - 1;
            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if(sum == 0){
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    //去重
                    while(left < right && nums[left] == nums[left+1]) left++;
                    while(left < right && nums[right] == nums[right-1]) right--;  
                    left++;
                    right--;                  
                }else if (sum > 0){
                    right--;
                }else{
                    left++;
                }
            }
        }
        return ans;
    }
}

复杂度分析：

时间复杂度：，其中 N 是数组 nums 的长度。

空间复杂度：。我们忽略存储答案的空间，额外的排序的空间复杂度为 。然而我们修改了输入的数组 nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序，空间复杂度为 。