前言

仅记录学习笔记，如有错误欢迎指正。

题目

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

示例

• 输入: [-1, 0, 1, 2, -1, -4]
• 输出:[
  [-1, 0, 1],
  [-1, -1, 2]
  ]

解法一

双指针来找

  public static List<List<Integer>> function(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int N = nums.length;
        for(int i =0;i<nums.length;i++){
            if(i>0 && nums[i-1] == nums[i]){
                continue;
            }
            int m = i+1;
            int n  = N-1;
            while(m < n){
                if(nums[i] + nums[m] + nums[n] < 0){
                    while(m < n && nums[m] == nums[m+1]){
                        m++;
                    }
                    m++;
                }else if (nums[i] + nums[m] + nums[n] > 0){
                    while(m < n && nums[n] == nums[n-1]){
                        n--;
                    }
                    n--;
                }else{
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[m]);
                    list.add(nums[n]);
                    res.add(list);
                    while(m < n && nums[m] == nums[m+1]){
                        m++;
                    }
                    while(m < n && nums[n] == nums[n-1]){
                        n--;
                    }
                    m++;
                    n--;
                }
            }
        }
        return res;
    }

  

解法二

dfs

  //dfs
    private static  List<List<Integer>> res = new ArrayList<>();
    private static  List<Integer> path = new ArrayList<>();
    public static List<List<Integer>> function1(int[] nums) {

        Arrays.sort(nums);
        int N = nums.length;
        boolean[] flag= new boolean[N+1];
        backTracking(nums,flag,0);
        return res;
    }

    private static void backTracking(int[] nums, boolean[] flag, int start) {
        if(path.size() == 3){
            int num = 0;
            for(int n : path){
                num += n;
            }
            if(num == 0){
                //new！
                res.add(new ArrayList<>(path));
            }
            //终止递归
            return;
        }
        for(int i = start;i<nums.length;i++){
            //剪枝
            if(i >0 && nums[i] == nums[i-1] && !flag[i-1] ){
                continue;
            }
            path.add(nums[i]);
            flag[i] = true;
            backTracking(nums,flag,i+1);
            flag[i] = false;
            path.remove(path.size()-1);
        }

    }