2475. 数组中不等三元组的数目 (opens new window)

1.dfs+回溯

分析：每种元素都有两种选择，选或者不选。搜索时需要开辟数组空间记录使用位。时间复杂度比较高。

class Solution {
    int res=0;
    public int unequalTriplets(int[] nums) {
        List<Integer> list=new ArrayList<>();
        dfs(nums,list,0);
        return res;
    }
    public void dfs(int[] nums,List<Integer> list,int index){
        if(list.size()==3){
            res++;
            return;
        }
        if(index==nums.length) return;
        if(!list.contains(nums[index])){
            list.add(nums[index]);
            dfs(nums,list,index+1);
            list.remove(list.size()-1);
        }
        dfs(nums,list,index+1);
    }
}

2.排序

分析：先对数组进行排序，使数组中相同的元素都相邻。

每次找到三元组的中间位置的元素，假设该相同元素起点为start，终点为end，那么三元素的组合数为(start)*(end-start+1)*(nums.length-1-end)。注意这里不需要考虑三元组两侧位置所选择元素是否相同，因为不论相同不同，只要索引都是不同的，那么都可以算作一种方案。

✨ 当进行区域划分、模块组合时，如果需要划分区域的个数为3，需要敏感一些，因为首尾两头的方案数往往不需要枚举计算，我们只需要找到中间位置。那么三个区域自然而然就能够自动划分出来。

class Solution {
    public int unequalTriplets(int[] nums) {
        Arrays.sort(nums);
        int res=0,start=0,end=0;
        while(start<nums.length){
            end=start;
            for(;end+1<nums.length&&nums[end]==nums[end+1];end++);
            res+=(start)*(end-start+1)*(nums.length-1-end);
            start=end+1;
        }
        return res;
    }
}

3.哈希

思路本质上就是上面的“三取中”的做法，只不过把排序聚合相同元素的过程用哈希代替。从而减小时间复杂度为O(n)。

class Solution {
    public int unequalTriplets(int[] nums) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        int res=0,pre=0;
        for(Integer a:map.values()){
            res+=pre*a*(nums.length-pre-a);
            pre+=a;
        }
        return res;
    }
}