题解 | #牛牛的三元组问题#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型二维数组
     */
    public int[][] findTriplets (int[] nums) {
        // write code here
        Arrays.sort(nums);
        List<Integer> path=new ArrayList<>();
        List<int[]> list=new ArrayList<>();
        boolean[] used=new boolean[nums.length];
        backTrack(0, used, nums, path, list);
        return list.toArray(new int[list.size()][3]);
    }

    private void backTrack(int start, boolean[] used, int[] nums,
     List<Integer> path, List<int[]> list){
        if(path.size()==3){
            int sum=path.get(0)+path.get(1)+path.get(2);
            if(sum==0){
                int[] tmp=new int[3];
                for (int i = 0; i < 3; i++)
                    tmp[i] = path.get(i);
                list.add(tmp);
            }
            return;
        }
        for(int i=start; i<nums.length; i++){
            if(used[i] || i>0 && nums[i-1]==nums[i] &&!used[i-1])continue;
            
            used[i]=true;
            path.add(nums[i]);
            backTrack(i, used, nums, path, list);
            used[i]=false;
            path.remove(path.size()-1);

        }
    }
}

这道题的关键是这个判断if(used[i] || i>0 && nums[i-1]==nums[i] && !used[i-1])continue; 通过这个判断可以去除重复的结果，比如nums=[-4,-1,-1,0,1,2]这个测试用例，used[i]只用来保证同一个索引处的元素只能被用一次，如果只是用used[i]判断是否元素用过，会出现两个[-1,0,1]的答案，因为索引1处的元素-1使用过，我们要保证不同索引处的相同值的元素被使用一次。