Medium

题目描述

给你一个由正整数组成的数组 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 中不同特殊子序列的数量。

示例 1：

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

示例 2：

输入：nums = [3,4,3,4,3,4,3,4]
输出：3
解释：
nums 中有三个特殊子序列。
- (p, q, r, s) = (0, 2, 4, 6)：对应元素 (3, 3, 3, 3)
- (p, q, r, s) = (1, 3, 5, 7)：对应元素 (4, 4, 4, 4)  
- (p, q, r, s) = (0, 2, 5, 7)：对应元素 (3, 3, 4, 4)

约束条件：

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

解题思路

这是一个比例匹配问题。核心思路是将条件 nums[p] * nums[r] == nums[q] * nums[s] 重写为 nums[p] / nums[q] == nums[s] / nums[r]，即寻找具有相同比例的配对。

算法思路：

  1. 比例化简：为避免浮点数精度问题，使用最大公约数(GCD)来表示比例。对于比例 a/b，我们用 (a/gcd(a,b), b/gcd(a,b)) 来唯一表示。

  2. 枚举策略：

    • 外层循环枚举所有可能的 (p,q) 对，满足 q - p > 1
    • 对于每个 (p,q)，计算比例 ratio1 = nums[p] / nums[q]
    • 内层循环枚举所有可能的 (r,s) 对，满足 r - q > 1 且 s - r > 1
    • 计算比例 ratio2 = nums[s] / nums[r]
    • 如果 ratio1 == ratio2，则找到一个有效子序列

  3. 优化：使用哈希表可以进一步优化，先预处理所有可能的 (r,s) 对及其比例，然后对每个 (p,q) 查询匹配的比例数量。

时间复杂度：O(n⁴) 的暴力枚举在给定约束下是可行的，因为 n ≤ 1000。

推荐解法：直接暴力枚举，代码简洁且在题目约束下效率足够。

代码实现

class Solution {
public:
    long long numberOfSubsequences(vector<int>& nums) {
        int n = nums.size();
        long long count = 0;
        
        auto gcd = [](int a, int b) -> int {
            while (b) {
                a %= b;
                swap(a, b);
            }
            return a;
        };
        
        auto getRatio = [&](int a, int b) -> pair<int, int> {
            int g = gcd(a, b);
            return {a / g, b / g};
        };
        
        for (int p = 0; p < n; p++) {
            for (int q = p + 2; q < n; q++) {
                auto ratio1 = getRatio(nums[p], nums[q]);
                
                for (int r = q + 2; r < n; r++) {
                    for (int s = r + 2; s < n; s++) {
                        auto ratio2 = getRatio(nums[s], nums[r]);
                        
                        if (ratio1 == ratio2) {
                            count++;
                        }
                    }
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def numberOfSubsequences(self, nums: List[int]) -> int:
        import math
        
        n = len(nums)
        count = 0
        
        def get_ratio(a, b):
            g = math.gcd(a, b)
            return (a // g, b // g)
        
        for p in range(n):
            for q in range(p + 2, n):
                ratio1 = get_ratio(nums[p], nums[q])
                
                for r in range(q + 2, n):
                    for s in range(r + 2, n):
                        ratio2 = get_ratio(nums[s], nums[r])
                        
                        if ratio1 == ratio2:
                            count += 1
        
        return count

public class Solution {
    public long NumberOfSubsequences(int[] nums) {
        int n = nums.Length;
        long count = 0;
        
        int Gcd(int a, int b) {
            while (b != 0) {
                int temp = b;
                b = a % b;
                a = temp;
            }
            return a;
        }
        
        (int, int) GetRatio(int a, int b) {
            int g = Gcd(a, b);
            return (a / g, b / g);
        }
        
        for (int p = 0; p < n; p++) {
            for (int q = p + 2; q < n; q++) {
                var ratio1 = GetRatio(nums[p], nums[q]);
                
                for (int r = q + 2; r < n; r++) {
                    for (int s = r + 2; s < n; s++) {
                        var ratio2 = GetRatio(nums[s], nums[r]);
                        
                        if (ratio1.Item1 == ratio2.Item1 && ratio1.Item2 == ratio2.Item2) {
                            count++;
                        }
                    }
                }
            }
        }
        
        return count;
    }
}

var numberOfSubsequences = function(nums) {
    const n = nums.length;
    let count = 0;
    
    for (let p = 0; p < n - 6; p++) {
        for (let q = p + 2; q < n - 4; q++) {
            for (let r = q + 2; r < n - 2; r++) {
                for (let s = r + 2; s < n; s++) {
                    if (nums[p] * nums[r] === nums[q] * nums[s]) {
                        count++;
                    }
                }
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n⁴ × log(max(nums)))
空间复杂度O(1)

说明：

  • 时间复杂度：四层嵌套循环为 O(n⁴)，每次比较需要计算 GCD，复杂度为 O(log(max(nums)))
  • 空间复杂度：只使用了常量级别的额外空间

相关题目