题目描述

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

思路

1. 如果数组长度 < 3，返回空数组;
2. 对数组排序；
3. 遍历数组，采用双指针，L指向i + 1, R指向n - 1, while (L < R)时判断nums[i] + nums[L] + nums[R]:
   1. 如果和 > 0，说明nums[R]太大，R—；
   2. 如果和 < 0, 说明nums[L]太小， L++；
   3. 如果和 == 0， 添加进结果中，并且要去重：
      1. 开启while循环，如果L < R && nums[R - 1] == nums[R], R—
      2. 开启while循环，如果L < R && nums[L + 1] == nums[L], L++

public class Solution_15 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // 特殊判断
        if (nums.length < 3) {
            return result;
        }
        // 排序
        Arrays.sort(nums);
        // 遍历数组
        for (int i = 0; i < nums.length - 1; i++) {
            // 当nums[i] > 0时，说明后面的数全为正数，那么就不可能和为0，可以直接返回了
            if (nums[i] > 0) {
                return result;
            }
            // 如果相邻两个数相等，说明要么有重复解，要么都无解，直接continue跳过本次循环
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            // 当left < right时，遍历
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                // 和为0
                } else {
                    List<Integer> level = new ArrayList<>();
                    level.add(nums[i]);
                    level.add(nums[left]);
                    level.add(nums[right]);
                    result.add(level);
                    // 跳过重复解
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                }
            }
        }
        return result;
    }
}