2023.6.13 数组中不等三元组的数目-526互联

直接的思路是三重循环\(O(n^3)\)解决，由于数据范围是\(n \leq 100\)，所以\(n^3 \leq 10^6\)可以过。
如果想稍微优化一下的话，可以考虑下面两种思路，都是类似的：

排序，排完序后相同的元素会聚集到一起，假设他们聚集在了区间\([i, j]\)内。那\([0, i - 1]\)这一部分区间和\([j + 1, n]\)这部分区间和中间的元素肯定都不相同。此时可以根据乘法原理直接统计答案。遍历一遍，对每个聚集区间计算其贡献，累加即可。
哈希表，先遍历一次，预处理出所有元素的出现次数。然后遍历哈希表，哈希表获得当前元素出现次数v，用一个变量pre统计前面已经被遍历过的元素，那后面还没被遍历过且和当前元素不同的元素个数就是n - pre - v，对于每个元素都执行这个计算，累计贡献即可。

use std::collections::HashMap;

impl Solution {
    pub fn unequal_triplets(nums: Vec<i32>) -> i32 
    {
        let mut cnt = HashMap::new();
        for x in nums.iter() {
            cnt.entry(x).and_modify(|x| *x += 1).or_insert(1);
        }

        let n = nums.len();
        let (mut res, mut pre) = (0, 0);
        for (_, value) in cnt {
            res += pre * value * (n as i32 - pre - value);
            pre += value;
        }
        res
    }
}

数组