题目描述

给你一个只包含正整数的数组 nums。

特殊子序列 是一个长度为 4 的子序列，用下标 (p, q, r, s) 表示，它们满足 p < q < r < s，且这个子序列 必须 满足以下条件：

• nums[p] * nums[r] == nums[q] * nums[s]
• 相邻坐标之间至少间隔 一个 数字。换句话说，q - p > 1，r - q > 1 且 s - r > 1。

子序列指的是从原数组中删除零个或者更多元素后，剩下元素不改变顺序组成的数字序列。

请你返回 nums 中不同 特殊子序列 的数目。

样例

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

输出：1

解释：

nums 中只有一个特殊子序列。

(p, q, r, s) = (0, 2, 4, 6) ：
    对应的元素为 (1, 3, 3, 1) 。
    nums[p] * nums[r] = nums[0] * nums[4] = 1 * 3 = 3
    nums[q] * nums[s] = nums[2] * nums[6] = 3 * 1 = 3

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

输出：3

解释：

nums 中共有三个特殊子序列。

(p, q, r, s) = (0, 2, 4, 6) ：
    对应元素为 (3, 3, 3, 3) 。
    nums[p] * nums[r] = nums[0] * nums[4] = 3 * 3 = 9
    nums[q] * nums[s] = nums[2] * nums[6] = 3 * 3 = 9
(p, q, r, s) = (1, 3, 5, 7) ：
    对应元素为 (4, 4, 4, 4) 。
    nums[p] * nums[r] = nums[1] * nums[5] = 4 * 4 = 16
    nums[q] * nums[s] = nums[3] * nums[7] = 4 * 4 = 16
(p, q, r, s) = (0, 2, 5, 7) ：
    对应元素为 (3, 3, 4, 4) 。
    nums[p] * nums[r] = nums[0] * nums[5] = 3 * 4 = 12
    nums[q] * nums[s] = nums[2] * nums[7] = 3 * 4 = 12

限制

• 7 <= nums.length <= 1000
• 1 <= nums[i] <= 1000

算法

(枚举，前后缀分解) $O((U^2 + n^2) \log U)$

1. 通过朴素筛法，提前预处理 $U^2$ 范围内每个数字的所有因数。
2. 枚举 p 和 r 的位置，在枚举 r 的过程中动态维护 q 和 s 合法区间的哈希表。
3. 枚举 $nums(p) \cdot nums(r)$ 的因数，并从 q 的区间和 s 的区间的哈希表中计算答案数。

时间复杂度

• 预处理的时间复杂度为 $O(U^2 \log U)$。
• 枚举的时间复杂度为 $O(n^2)$，每次枚举因数的时间复杂度为 $O(\log U)$。
• 故总时间复杂度为 $O((U^2 + n^2) \log U)$。

空间复杂度

• 需要 $O(U^2)$ 的额外空间存储预处理的因数和哈希表。

C++ 代码

#define LL long long

const int U = 1001, T = 1000001;

vector<int> p[T];

auto init = []{
    for (int i = 1; i < T; i++)
        for (int j = i; j < T; j += i)
            p[j].push_back(i);

    return 0;
}();

class Solution {
public:
    LL numberOfSubsequences(vector<int>& nums) {
        const int n = nums.size();
        int mid[U], suf[U];
        memset(mid, 0, sizeof(mid));
        memset(suf, 0, sizeof(suf));

        LL ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = n - 1; j >= i + 6; j--)
                ++suf[nums[j]];

            for (int j = i + 4; j < n - 2; j++) {
                ++mid[nums[j - 2]];

                int x = nums[i] * nums[j];
                for (int t : p[x]) {
                    if (t >= U)
                        break;

                    if (x / t < U)
                        ans += (LL)(mid[t]) * suf[x / t];
                }

                --suf[nums[j + 2]];
            }

            for (int j = i + 2; j < n - 4; j++)
                --mid[nums[j]];
        }

        return ans;
    }
};