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：

输入：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 。

提示：

3 <= nums.length <= 100
1 <= nums[i] <= 1000

思路

暴力模拟

暴力解答没什么好说的

暴力模拟优化

前两位相同直接跳过

数组替代哈希表

实质组合，排序后通过 pre × c × (len − pre − c)

pre: 已遍历不同数值的元素个数
c: 当前遍历相同数值的元素个数
len - pre - c: 未遍历不同数值的元素个数

“简化”成有效的二元数组看待

将三元数组判断转化为两元数组看待，核心代码如下

// 用来统计已经遍历过的数值出现的次数
int[] counts = new int[1001]

// 把之前存在数字一样的两位数组过滤掉
result += two - counts[nums[i]] * (i - counts[nums[i]]);

// 之前可组成的两位不同数组的数目
two += i - counts[nums[i]];

// 数值出现次数+1
counts[nums[i]]++;

例如：{8, 8, 7, 9, 8, 5, 7, 1, 1}

i = 0

nums[i] => 8

result = 0 + 0 - 0 * (0 - 0) => 0

two = 0 + 0 - 0 => 0

counts[8] = 0 + 1 => 1

i = 1

nums[i] => 8

result = 0 + 0 - 1 * (1 - 1) => 0

two = 0 + 1 - 1 => 0

counts[8] = 1 + 1 => 2

i = 2

nums[i] => 7

result = 0 + 0 - 0 * (2 - 0) => 0

two = 0 + 2 - 0 => 2

counts[7] = 0 + 1 => 1

i = 3

nums[i] => 9

result = 0 + 2 - 0 * (3 - 0) => 2

two = 2 + 3 - 0 => 5

counts[9] = 0 + 1 => 1

i = 4

nums[i] => 8

result = 2 + 5 - 2 * (4 - 2) => 3

two = 5 + 4 - 2 => 7

counts[8] = 2 + 1 => 3

i = 5

nums[i] => 5

result = 3 + 7 - 0 * (5 - 0) => 10

two = 7 + 5 - 0 => 12

counts[5] = 0 + 1 => 1

i = 6

nums[i] => 7

result = 10 + 12 - 1 * (6 - 1) => 17

two = 12 + 6 - 1 => 17

counts[7] = 1 + 1 => 2

i = 7

nums[i] => 1

result = 17 + 17 - 0 * (7 - 0) => 34

two = 17 + 7 - 0 => 24

counts[1] = 0 + 1 => 1

i = 8

nums[i] => 1

result = 34 + 24 - 1 * (8 - 1) => 51

two = 24 + 8 - 1 => 31

counts[1] = 1 + 1 => 2

代码

暴力模拟

class Solution {
    public int unequalTriplets(int[] nums) {
        int res = 0, n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] != nums[j] && nums[i] != nums[k] && nums[j] != nums[k]) {
                        res++;
                    }
                }
            }
        }
        return res;
    }
}

暴力模拟优化

class Solution {
    public int unequalTriplets(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    continue;
                }
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] == nums[k] || nums[j] == nums[k]) {
                        continue;
                    }
                    result++;
                }
            }
        }
        return result;
    }
}

数组替代哈希表

class Solution {
    public int unequalTriplets(int[] nums) {
        int result = 0;
        int[] counts = new int[1001];
        for (int num : nums) {
            counts[num]++;
        }
        int pre = 0;
        int len = nums.length;
        for (int count : counts) {
            if (count == 0) {
                continue;
            }
            result += pre * count * (len - pre - count);
            pre += count;
        }
        return result;
    }
}

“简化”成有效的二元数组

class Solution {
    public int unequalTriplets(int[] nums) {
        int result = 0;
        int two = 0;
        int[] counts = new int[1001];
        for (int i = 0; i < nums.length; i++) {
            // 把之前存在数字一样的两位数组过滤掉
            result += two - counts[nums[i]] * (i - counts[nums[i]]);
            // 之前可组成的两位不同数组的数目
            two += i - counts[nums[i]];
            counts[nums[i]]++;
        }
        return result;
    }
}