题目描述

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

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [   [-1, 0, 1],   [-1, -1, 2] ]

https://leetcode-cn.com/problems/3sum/

解法1

首先对原数组nums进行排序, 用指针i指向nums的每个元素, 然后另指针j=i+1, k=|nums|-1. 指针j与k相向而行, 直到nums[i]+nums[j]+nums[k] == 0我们就找到了一个解, 此时需要继续相向而行直到k>=j. 将数组排序可以把算法的时间复杂度降低到O(n^2). 若不对数组排序, 为了寻找j, k使得nums[i]+nums[j]+nums[k] == 0, 需要使用双重循环遍历nums, 这样会使复杂度达到O(n^3).

因为题目要求“不可以包含重复的三元组”, 这就需要我们一旦找到符合条件的i, j, k. 就需要跳过nums中相同的元素(代码中被标记的部分), 以避免寻找重复的解.

例如 nums = [-1, 0, 1, 2, -1, -4], 排序后nums = [-4, -1, -1, 0, 1, 2]. 当i=1, j=2, k=5使得nums[1]+nums[2]+nums[5]==0, 寻找的其中的一个解{-1, -1, 2}; 当i=1, j=3, k=4使得nums[1]+nums[3]+num[4]找到另一个解{-1, 0, 1}. 此时, 内层循环结束, 下一次外层循环i=2, 我们又会找到重复的解{-1, 0, 1}, 而这个解在i=1使已经被找到了. 为了避免重复的解被计算, 我们需要在内层循环与外层循环找到解后, 都要跳过重复的元素, 以避免解被重复发现.

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++) {
            int num = nums[i];
            int j = i + 1;
            int k = nums.length - 1;

            while (j < k) {
                int l = nums[j];
                int r = nums[k];
                int sum = l + r + num;

                if (sum == 0) {
                    List<Integer> e = new ArrayList<>();
                    e.add(nums[j]);
                    e.add(nums[k]);
                    e.add(num);
                    res.add(e);

                    do
                        j++;
                    while (j < k && nums[j] == l);

                    do
                        k--;
                    while (k > j && nums[k] == r);
                } else if (sum < 0)
                    j++;
                else
                    k--;

            }

            while (i + 1 < nums.length && nums[i + 1] == num)
                i++;
        }
        return res;
    }
}