leetcode-15：三数之和

问题

给你一个包含 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]
输出：[]

思路

题目中要求我们找到所有不重复且和为的三元组，这个不重复的要求使得我们

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

不重复的本质是什么？我们保持三重循环的大框架不变，只需要保证：

• 第二重循环枚举到的元素不小于当前第一重循环枚举到的元素
• 第三重循环枚举到的元素不小于当前第二重循环枚举到的元素

也就是说，我们枚举的三元组满足，保证了只有这个顺序会被枚举到，而、等等这些不会，这样就减少了重复。要实现这一点，我们可以将数组中的元素从小到大进行排序，随后使用普通的三重循环就可以满足上面的要求

同时，对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复。举个例子，如果排完序的数组为
，我们使用三重循环枚举到的第一个三元组为，如果第三重循环继续枚举下一个元素，那么仍然是三元组，产生了重复。因此我们需要将第三重循环跳到下一个不相同的元素，即数组中的最后一个元素，枚举三元组。这种方法的时间复杂度仍然为，毕竟我们还是没有跳出三重循环的大框架。然而它是很容易继续优化的，可以发现，如果我们固定了前两重循环枚举到的元素和，那么只有唯一的满足。当第二重循环往后枚举一个元素时，由于，那么满足的一定有，即在数组中一定出现在的左侧。也就是说，我们可以从小到大枚举，同时从大到小枚举，即第二重循环和第三重循环实际上是并列的关系

有了这样的发现，我们就可以保持第二重循环不变，而将第三重循环变成一个从数组最右端开始向左移动的指针，
也就是我们常说的双指针，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从减少至（这是因为在枚举的过程每一步中，左指针会向右移动一个位置（也就是题目中的），而右指针会向左移动若干个位置，这个与数组的元素有关，但我们知道它一共会移动的位置数为，均摊下来，每次也向左移动一个位置，时间复杂度为

包括第一层循环在内，枚举的总时间复杂度为。由于排序的时间复杂度为，因此算法的总时间复杂度为

我们需要保持左指针一直在右指针的左侧（）

官方题解

package leetcode_15;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public 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 first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = - nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }
}

自解

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {// 总时间复杂度：O(n^2)
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length <= 2) 
            return ans;
        Arrays.sort(nums); // O(nlogn)
        for (int i = 0; i < nums.length - 2; i++) { // O(n^2)
            if (nums[i] > 0) 
                break; // 第一个数大于 0，后面的数都比它大，肯定不成立了
            if (i > 0 && nums[i] == nums[i - 1]) 
                continue; // 去掉重复情况
            int target = -nums[i];
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] == target) {
                    ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
             // 现在要增加 left，减小 right，但是不能重复，比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3
                    left++; right--; // 首先无论如何先要进行加减操作
                    while (left < right && nums[left] == nums[left - 1]) 
                        left++;
                    while (left < right && nums[right] == nums[right + 1]) 
                        right--;
                } 
                else if (nums[left] + nums[right] < target) {
                    left++;
                } 
                else {  // nums[left] + nums[right] > target
                    right--;
                }
            }
        }
        return ans;
    }
}

• 时间复杂度：，其中是数组的长度
• 空间复杂度：。忽略了存储答案的空间，额外的排序的空间复杂度为。也可以看成使用了一个额外的数组存储了数组的副本并进行排序，空间复杂度为