2475. 数组中不等三元组的数目-快速排序+遍历求和_2475 数组中不等三元组的数目

2475. 数组中不等三元组的数目-快速排序+遍历求和
      给你一个下标从 0 开始的正整数数组 nums 。请你找出并统计满足下述条件的三元组 (i, j, k) 的数目：

0 <= i < j < k < nums.length
nums[i]、nums[j] 和 nums[k] 两两不同 。
    换句话说：nums[i] != nums[j]、nums[i] != nums[k] 且 nums[j] != nums[k] 。
1
2
3

返回满足上述条件三元组的数目。

示例 1：

输入：nums = [4,4,2,4,3]
输出：3
解释：下面列出的三元组均满足题目条件：

• (0, 2, 4) 因为 4 != 2 != 3
• (1, 2, 4) 因为 4 != 2 != 3
• (2, 3, 4) 因为 2 != 4 != 3
  共计 3 个三元组，返回 3 。
  注意 (2, 0, 4) 不是有效的三元组，因为 2 > 0 。

示例 2：

输入：nums = [1,1,1,1,1]
输出：0
解释：不存在满足条件的三元组，所以返回 0 。

这一题其实就没什么难的，我们排完序之后，求和就可以啦，解题代码如下：

void quick(int *a,int low,int high){
    if(low<high){
        int l=low,h=high,p=a[low];
        while(low<high){
            while(low<high&&a[high]>=p){
                high--;
            }
            a[low]=a[high];
            while(low<high&&a[low]<=p){
                low++;
            }
            a[high]=a[low];
        }
        a[low]=p;
        quick(a,l,low-1);
        quick(a,low+1,h);
    }
}

int unequalTriplets(int* nums, int numsSize){
    quick(nums,0,numsSize-1);
    int a[numsSize];
    int size=0;
    int sum=0;
    int start=nums[0];
    int count =1;
    
    for(int i=1;i<numsSize;i++){
      
        if(nums[i]!=start){
            sum=sum*count;
             a[size++]=count;
            count=1;
            start=nums[i];
        }
        else{
            count++;
        }
    }
     a[size++]=count;
    if(size<3){
        return 0;
    }
   
    for(int i=0;i<size;i++){
                for(int j=i+1;j<size;j++){
                     for(int k=j+1;k<size;k++){
                         sum=sum+a[i]*a[j]*a[k];        
                     }
                
           }

    }

   
return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57