↓Skip to main content
  1. Posts/

LeetCode-3404 统计特殊子序列的数目

·1 min·
Table of Contents

LeetCode-3404 统计特殊子序列的数目 #

Solution 1 #

4 个坐标, 暴力枚举显然不可行. 将 $nums[p]*nums[r] == nums[q] * nums[s]$ 改写为 $$ \frac{nums[p]}{nums[q]} = \frac{nums[s]}{nums[r]} $$ 枚举 $r$, 维护左侧 $p, q$ . 对于 $s$, 用哈希表维护 $(p, r-2)$ 的对即可, 因为 $(p, r-t), t>2$ 的对在枚举 $r-1$ 时已经更新到哈希表中了. 逻辑是枚举 $r$, 更新哈希表, 然后枚举 $s$, 更新答案.

代码如下:

class Solution:
    def numberOfSubsequences(self, nums: List[int]) -> int:
        def frac(x, y):
            z = gcd(x, y)
            return x // z, y // z
        ans = 0
        n = len(nums)
        count = defaultdict(int)
        for i in range(4, n - 2):
            for k in range(i - 3):
                count[frac(nums[k], nums[i - 2])] += 1
            for j in range(i + 2, n):
                ans += count[frac(nums[j], nums[i])]
        return ans