[LeetCode][2475. 数组中不等三元组的数目] 2种 O(n) 时间复杂度算法

By Long Luo

今天 LeetCode 第320场周赛 中第一题是 2475. 数组中不等三元组的数目 ，本文是该题的题解，同时发表在 这里 。

参考了 @灵茶山艾府 的题解 非暴力做法 ，实际上我们可以不用先排序，而是先用 $\texttt{HashMap}$ 统计数组 $\textit{num}$ 元素频率。

之后遍历 $\texttt{HashMap}$ ，结果为：$\sum_{j = 0}^{n} (map[0] + \cdots + map[i]) \times map[j] \times (map[k] + \cdots + map[n - 1])$ ，其中 $n$ 为 $\textit{nums}$ 的长度。

证明如下：

对于数组中的元素 $x$ ，可以得到：

• 小于 $x$ 的数有 $a$ 个；
• 等于 $x$ 的数有 $b$ 个；
• 大于 $x$ 的数有 $c$ 个。

那么 $x$ 对最终答案的贡献是 $abc$ 。

即使 $x$ 是三元组中的最大或最小值，由于 $i, j, k$ 的对称性，很明显其实和 $x$ 是中间值都是同一个答案。

证毕！

class Solution {
    public int unequalTriplets(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int x : nums) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }

        int ans = 0;

        int left = 0;
        int right = nums.length;

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int cnt = entry.getValue();

            right -= cnt;
            ans += left * cnt * right;
            left += cnt;
        }

        return ans;
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为 $\textit{nums}$ 的长度。
• 空间复杂度：$O(n)$ 。

数学：组合

在方法一的基础上，实际上我们还有一种更快的方法，就是利用中学数学里学过的 排列组合 .

详细题解：The Fastest O(n) Solution: Math Combinations 。

代码如下所示：

class Solution {
    public int unequalTriplets(int[] nums) {
        int n = nums.length;

        Map<Integer, Integer> map = new HashMap<>();

        for (int x : nums) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }

        // total combinations
        int ans = n * (n - 1) * (n - 2) / 6;

        for (int cnt : map.values()) {
            if (cnt < 2) {
                continue;
            }

            int same3cnt = cnt * (cnt - 1) * (cnt - 2) / 6;
            int same2cnt = (n - cnt) * cnt * (cnt - 1) / 2;
            ans -= same3cnt + same2cnt;
        }

        return ans; 
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为 $\textit{nums}$ 的长度。
• 空间复杂度：$O(n)$ 。

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗