题目描述

给你一个整数数组 nums，请你求出 nums 中大小为 5 的子序列的数目，它是 唯一中间众数序列。

由于答案可能很大，请你将答案对 10^9 + 7 取余 后返回。

众数 指的是一个数字序列中出现次数 最多 的元素。

如果一个数字序列众数只有一个，我们称这个序列有 唯一众数。

一个大小为 5 的数字序列 seq，如果它中间的数字（seq[2]）是唯一众数，那么称它是 唯一中间众数 序列。

子序列 指的是将一个数组删除一些（也可以不删除）元素后，剩下元素不改变顺序得到的 非空 数组。

样例

输入：nums = [1,1,1,1,1,1]

输出：6

解释：

[1, 1, 1, 1, 1] 是唯一长度为 5 的子序列。1 是它的唯一中间众数。有 6 个这样的子序列，所以返回 6。

输入：nums = [1,2,2,3,3,4]

输出：4

解释：

[1, 2, 2, 3, 4] 和 [1, 2, 3, 3, 4] 都有唯一中间众数，
    因为子序列中下标为 2 的元素在子序列中出现次数最多。
[1, 2, 2, 3, 3] 没有唯一中间众数，因为 2 和 3 都出现了两次。

输入：nums = [0,1,2,3,4,5,6,7,8]

输出：0

解释：

没有长度为 5 的唯一中间众数子序列。

限制

• 5 <= nums.length <= 1000
• -10^9 <= nums[i] <= 10^9

算法

(反向处理，哈希表，分类讨论) $O(n^2)$

1. 由于限制条件里中间位置较为关键，所以考虑枚举中间位置的数字。
2. 但正向计算情况比较多，也很复杂，考虑反向计算不符合条件的五元组。
3. 情形一：中间位置的数字为 $x$，则剩下四个位置都不为 $x$。
4. 情形二：中间位置的数字为 $x$，还有一个位置为 $x$，此时枚举另一个不同的数字 $y$。
   1. 两个 $y$ 在 $x$ 左边，另一个 $x$ 在右边，右边剩余一个数字非 $x$（可以为 $y$）。
   2. 两个 $y$ 在 $x$ 右边，另一个 $x$ 在左边，右边剩余一个数字非 $x$（可以为 $y$）。
   3. 一边一个 $y$，另一个 $x$ 在左边，右边剩余一个数字非 $x$ 非 $y$。
   4. 一边一个 $y$，另一个 $x$ 在右边，左边剩余一个数字非 $x$ 非 $y$。
5. 使用哈希表动态维护前缀和后缀数字的出现个数。

时间复杂度

• 预处理的时间复杂度为 $O(n)$。
• 遍历枚举的时间复杂度为 $O(n^2)$。
• 故总时间复杂度为 $O(n^2)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储哈希表。

C++ 代码

const int mod = 1000000007;

#define LL long long

class Solution {
private:
    inline int C2(int x) {
        return x * (x - 1) / 2;
    }

public:
    int subsequencesWithMiddleMode(vector<int>& nums) {
        const int n = nums.size();

        unordered_map<int, int> pre, suf;
        for (int x : nums)
            ++suf[x];

        LL ans = (LL)(n) * (n - 1) * (n - 2) * (n - 3) * (n - 4) / 120;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            --suf[x];

            // o o x o o
            ans -= (LL)C2(i - pre[x]) * C2(n - i - 1 - suf[x]);

            for (const auto &[y, _] : suf) {
                if (y == x)
                    continue;

                // y y x x (o,y)
                ans -= (LL)C2(pre[y]) * suf[x] * (n - i - 1 - suf[x]);
                // (o,y) x x y y
                ans -= (LL)C2(suf[y]) * pre[x] * (i - pre[x]);
                // y x x y o
                ans -= (LL)(pre[y]) * suf[y] * pre[x] * (n - i - 1 - suf[x] - suf[y]);
                // y o x x y
                ans -= (LL)(pre[y]) * suf[y] * suf[x] * (i - pre[x] - pre[y]);
            }

            ++pre[x];
        }

        return ans % mod;
    }
};