1、前言

本题错误的思路是用回溯来做，回溯做不仅复杂度高而且还需要判断重复的 list（list 中位置不同还是数字相同的数还是算一个）。

class Solution {

    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> threeSum(int[] nums) {
        if(nums == null || nums.length == 0){
            return null;
        }
        ArrayList<Integer> list = new ArrayList<>();
        dfs(0, 0, nums, list);
        return res;
    }

    private void dfs(int level, int index, int[] nums, ArrayList<Integer> list){
        if(level == 3){
            if(isValidSum(list)){
                res.add(new ArrayList<>(list));
            }
            
            return;
        }

        for(int i = index; i < nums.length; i++){
            list.add(nums[i]);
            dfs(level + 1, i + 1, nums, list);
            list.remove(list.size() - 1);
        }
    }

    private boolean isValidSum(ArrayList<Integer> list){
        int sum = 0;
        for(int i : list){
            sum += i;
        }
        return sum == 0;
    }
}

题目描述

2、思路

首先对数组进行排序，排序后固定从数组左边开始的一个数 $nums[i]$ ，再使用左右指针指向 $nums[i]$ 右边的两端，数字分别为 $nums[L]$ 和 $nums[R]$ ，计算三个数的和 $sum$ 判断是否满足0，满足则添加进结果集

如果 $nums[i]$ 大于0，则三数之和必然无法等于0，结束循环。

如果 $nums[i] == nums[i - 1]$ （当前数与自己上一个数相比），则说明数字重复，会导致结果重复，所以应该跳过。

当 $sum == 0$ 时， $nums[L] == nums[L + 1]$ 则会导致结果重复，应该跳过， $L++$

当 $sum == 0$ 是， $nums[R] == nums[R - 1]$ 则会导致结果重复，应该跳过， $R--$

3、代码

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length < 3){
            return res;
        }

        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > 0){
                break;
            }
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int L = i + 1;
            int R = nums.length - 1;
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == 0){
                    res.add(Arrays.asList(nums[i], nums[L], nums[R]));
                    while(L < R && nums[L] == nums[L + 1]){
                        L++;
                    }
                    while(L < R && nums[R] == nums[R - 1]){
                        R--;
                    }
                    L++;
                    R--;
                }else if(sum < 0){
                    L++;
                }else{
                    R--;
                }
            }
        }
        return res;
    }
}