2025-07-13：统计特殊子序列的数目。用go语言，给定一个只包含正整数的数组 nums，我们定义长度为4的特殊子序列，其下标为 (p, q, r, s)，且满足以下条件：

• o p < q < r < s
• o 位置之间至少间隔一个元素，即 q - p > 1，r - q > 1，s - r > 1
• o 该四元组对应的值满足等式：nums[p] * nums[r] = nums[q] * nums[s]

这里的子序列是指在数组中删除0个或多个元素后，保持剩余元素顺序不变得到的序列。

任务是计算数组中满足上述条件的不同特殊子序列的数量。

7 <= nums.length <= 1000。

1 <= nums[i] <= 1000。

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

题目来自力扣3404。

解决思路

为了高效地统计满足条件的四元组，我们需要避免暴力枚举所有可能的四元组（时间复杂度为 O(n^4)），而是采用更聪明的方法。以下是分步描述：

1. 理解四元组的结构

四元组 (p, q, r, s) 需要满足：

o p < q - 1

o q < r - 1

o r < s - 1

o nums[p] * nums[r] = nums[q] * nums[s]

2. 重新排列等式

将等式 nums[p] * nums[r] = nums[q] * nums[s] 重新排列为：
nums[p] / nums[q] = nums[s] / nums[r]
这样可以将问题转化为：对于固定的 q 和 r，统计满足 nums[p] / nums[q] = nums[s] / nums[r] 的 p 和 s 的数量。

3. 枚举 q 和 r

o q 和 r 是四元组的中间两个元素，且需要满足 q < r - 1。

o 为了满足 q - p > 1 和 s - r > 1，p 的取值范围是 [0, q - 2]，s 的取值范围是 [r + 2, n - 1]。

4. 预处理和哈希表

o 对于固定的 q 和 r，我们需要快速统计满足 nums[p] / nums[q] = nums[s] / nums[r] 的 p 和 s 的数量。

o 可以预先计算 nums[p] / nums[q] 的值并存储在哈希表中，然后对于每个 nums[s] / nums[r]，查找哈希表中匹配的值。

5. 具体步骤

o 外层循环枚举可能的 r 值（从 4 到 n - 3，因为 q 至少是 2，p 至少是 0，s 至少是 r + 2）。

o 对于每个 r，内层循环枚举 q 的值（从 2 到 r - 2）。

o 对于每个 (q, r) 对：

• 首先，遍历所有可能的 p（从 0 到 q - 2），计算 nums[p] / nums[q] 的值，并更新哈希表（计数）。
• 然后，遍历所有可能的 s（从 r + 2 到 n - 1），计算 nums[s] / nums[r] 的值，并在哈希表中查找匹配的 nums[p] / nums[q] 的数量，累加到结果中。
• 注意：哈希表需要在每次 (q, r) 对处理完成后清空，以避免重复计数。

6. 优化

o 可以通过增量式更新哈希表来优化。例如，当固定 r 并递增 q 时，可以逐步将新的 p 值（即 q - 2）对应的 nums[p] / nums[q] 加入哈希表。

o 类似地，可以固定 q 并递增 r，逐步将新的 s 值（即 r + 2）对应的 nums[s] / nums[r] 进行匹配。

时间复杂度

o 外层循环枚举 r：O(n)

o 内层循环枚举 q：O(n)

o 对于每个 (q, r) 对：

• 遍历 p：O(n)
• 遍历 s：O(n)

o 哈希表操作（插入和查询）平均为 O(1)
因此，总的时间复杂度为 O(n^3)。

空间复杂度

o 哈希表存储 nums[p] / nums[q] 的值，最多需要 O(n) 的空间。
因此，总的额外空间复杂度为 O(n)。

示例验证

以 nums = [1, 2, 3, 4, 3, 6, 1] 为例：

o 唯一满足条件的四元组是 (0, 2, 4, 6)：

• nums[0] * nums[4] = 1 * 3 = 3
• nums[2] * nums[6] = 3 * 1 = 3

o 其他组合不满足等式或间隔条件。

总结

通过枚举中间的两个点 q 和 r，并利用哈希表高效统计匹配的 p 和 s 的数量，可以在 O(n^3) 的时间复杂度和 O(n) 的额外空间复杂度内解决问题。

Go完整代码如下：

package main

import (
    "fmt"
)

func numberOfSubsequences(nums []int) (ans int64) {
    n := len(nums)
    cnt := map[float32]int{}
    // 枚举 b 和 c
    for i := 4; i < n-2; i++ {
        // 增量式更新，本轮循环只需枚举 b=nums[i-2] 这一个数
        // 至于更前面的 b，已经在前面的循环中添加到 cnt 中了，不能重复添加
        b := float32(nums[i-2])
        // 枚举 a
        for _, a := range nums[:i-3] {
            cnt[float32(a)/b]++
        }

        c := float32(nums[i])
        // 枚举 d
        for _, d := range nums[i+2:] {
            ans += int64(cnt[float32(d)/c])
        }
    }
    return
}

func main() {
    nums := []int{1, 2, 3, 4, 3, 6, 1}
    result := numberOfSubsequences(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

defnumberOfSubsequences(nums):
    from collections import defaultdict
    ans = 0
    n = len(nums)
    cnt = defaultdict(int)

    # 枚举 b 和 c
    for i inrange(4, n - 2):
        # 增量式更新，本轮循环只需枚举 b=nums[i-2] 这一个数
        b = nums[i - 2]
        # 枚举 a
        for a in nums[:i - 3]:
            cnt[a / b] += 1

        c = nums[i]
        # 枚举 d
        for d in nums[i + 2:]:
            ans += cnt[d / c]

    return ans


if __name__ == "__main__":
    nums = [1, 2, 3, 4, 3, 6, 1]
    result = numberOfSubsequences(nums)
    print(result)

·

我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。

欢迎关注“福大规模架构师每日一题”，让 Go 语言和算法助力您的职业发展

·