LeetCode 题解工作台
统计特殊子序列的数目
给你一个只包含正整数的数组 nums 。 特殊子序列 是一个长度为 4 的子序列，用下标 (p, q, r, s) 表示，它们满足 p ，且这个子序列 必须 满足以下条件： nums[p] * nums[r] == nums[q] * nums[s] 相邻坐标之间至少间隔 一个 数字。换句话说， q…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
class Solution: def numberOfSubsequences(self, nums: List[int]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个只包含正整数的数组 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 = 3nums[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)。 nums[p] * nums[r] = nums[0] * nums[4] = 3 * 3 = 9nums[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 = 16nums[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 = 12nums[q] * nums[s] = nums[2] * nums[7] = 3 * 4 = 12
- 对应元素为
提示：
7 <= nums.length <= 10001 <= nums[i] <= 1000
解题思路
方法一
class Solution:
def numberOfSubsequences(self, nums: List[int]) -> int:
n = len(nums)
cnt = defaultdict(int)
for r in range(4, n - 2):
c = nums[r]
for s in range(r + 2, n):
d = nums[s]
g = gcd(c, d)
cnt[(d // g, c // g)] += 1
ans = 0
for q in range(2, n - 4):
b = nums[q]
for p in range(q - 1):
a = nums[p]
g = gcd(a, b)
ans += cnt[(a // g, b // g)]
c = nums[q + 2]
for s in range(q + 4, n):
d = nums[s]
g = gcd(c, d)
cnt[(d // g, c // g)] -= 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Evaluating the candidate's ability to optimize ratio calculations using GCD.
- question_mark
Assessing the approach to using hash tables for efficient subsequence counting.
- question_mark
Looking for a clean solution that balances time complexity with correctness.
常见陷阱
外企场景- error
Overcomplicating the ratio calculation, missing the optimization using GCD.
- error
Inefficient brute-force enumeration of all subsequences.
- error
Incorrectly handling the array bounds and missing subsequences due to index errors.
进阶变体
外企场景- arrow_right_alt
What if the array length was increased significantly? The approach should scale accordingly.
- arrow_right_alt
How would the solution change if the array contained zeros or negative numbers?
- arrow_right_alt
What if subsequences of length other than 4 were required?