| comments | difficulty | edit_url | tags | ||||
|---|---|---|---|---|---|---|---|
true |
中等 |
|
给你一个只包含正整数的数组 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)：<ul> <li>对应的元素为 <code>(1, 3, 3, 1)</code> 。</li> <li><code>nums[p] * nums[r] = nums[0] * nums[4] = 1 * 3 = 3</code></li> <li><code>nums[q] * nums[s] = nums[2] * nums[6] = 3 * 1 = 3</code></li> </ul> </li>
示例 2：
输入：nums = [3,4,3,4,3,4,3,4]
输出：3
解释：
nums 中共有三个特殊子序列。
(p, q, r, s) = (0, 2, 4, 6)：<ul> <li>对应元素为 <code>(3, 3, 3, 3)</code> 。</li> <li><code>nums[p] * nums[r] = nums[0] * nums[4] = 3 * 3 = 9</code></li> <li><code>nums[q] * nums[s] = nums[2] * nums[6] = 3 * 3 = 9</code></li> </ul> </li> <li><code>(p, q, r, s) = (1, 3, 5, 7)</code> ： <ul> <li>对应元素为 <code>(4, 4, 4, 4)</code> 。</li> <li><code>nums[p] * nums[r] = nums[1] * nums[5] = 4 * 4 = 16</code></li> <li><code>nums[q] * nums[s] = nums[3] * nums[7] = 4 * 4 = 16</code></li> </ul> </li> <li><code>(p, q, r, s) = (0, 2, 5, 7)</code> ： <ul> <li>对应元素为 <code>(3, 3, 4, 4)</code> 。</li> <li><code>nums[p] * nums[r] = nums[0] * nums[5] = 3 * 4 = 12</code></li> <li><code>nums[q] * nums[s] = nums[2] * nums[7] = 3 * 4 = 12</code></li> </ul> </li>
提示：
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 ansclass Solution {
public long numberOfSubsequences(int[] nums) {
int n = nums.length;
Map<Integer, Integer> cnt = new HashMap<>();
for (int r = 4; r < n - 2; ++r) {
int c = nums[r];
for (int s = r + 2; s < n; ++s) {
int d = nums[s];
int g = gcd(c, d);
cnt.merge(((d / g) << 12) | (c / g), 1, Integer::sum);
}
}
long ans = 0;
for (int q = 2; q < n - 4; ++q) {
int b = nums[q];
for (int p = 0; p < q - 1; ++p) {
int a = nums[p];
int g = gcd(a, b);
ans += cnt.getOrDefault(((a / g) << 12) | (b / g), 0);
}
int c = nums[q + 2];
for (int s = q + 4; s < n; ++s) {
int d = nums[s];
int g = gcd(c, d);
cnt.merge(((d / g) << 12) | (c / g), -1, Integer::sum);
}
}
return ans;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}class Solution {
public:
long long numberOfSubsequences(vector<int>& nums) {
int n = nums.size();
unordered_map<int, int> cnt;
for (int r = 4; r < n - 2; ++r) {
int c = nums[r];
for (int s = r + 2; s < n; ++s) {
int d = nums[s];
int g = gcd(c, d);
cnt[((d / g) << 12) | (c / g)]++;
}
}
long long ans = 0;
for (int q = 2; q < n - 4; ++q) {
int b = nums[q];
for (int p = 0; p < q - 1; ++p) {
int a = nums[p];
int g = gcd(a, b);
ans += cnt[((a / g) << 12) | (b / g)];
}
int c = nums[q + 2];
for (int s = q + 4; s < n; ++s) {
int d = nums[s];
int g = gcd(c, d);
cnt[((d / g) << 12) | (c / g)]--;
}
}
return ans;
}
};func numberOfSubsequences(nums []int) (ans int64) {
n := len(nums)
cnt := make(map[int]int)
gcd := func(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
for r := 4; r < n-2; r++ {
c := nums[r]
for s := r + 2; s < n; s++ {
d := nums[s]
g := gcd(c, d)
key := ((d / g) << 12) | (c / g)
cnt[key]++
}
}
for q := 2; q < n-4; q++ {
b := nums[q]
for p := 0; p < q-1; p++ {
a := nums[p]
g := gcd(a, b)
key := ((a / g) << 12) | (b / g)
ans += int64(cnt[key])
}
c := nums[q+2]
for s := q + 4; s < n; s++ {
d := nums[s]
g := gcd(c, d)
key := ((d / g) << 12) | (c / g)
cnt[key]--
}
}
return
}function numberOfSubsequences(nums: number[]): number {
const n = nums.length;
const cnt = new Map<number, number>();
function gcd(a: number, b: number): number {
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}
for (let r = 4; r < n - 2; r++) {
const c = nums[r];
for (let s = r + 2; s < n; s++) {
const d = nums[s];
const g = gcd(c, d);
const key = ((d / g) << 12) | (c / g);
cnt.set(key, (cnt.get(key) || 0) + 1);
}
}
let ans = 0;
for (let q = 2; q < n - 4; q++) {
const b = nums[q];
for (let p = 0; p < q - 1; p++) {
const a = nums[p];
const g = gcd(a, b);
const key = ((a / g) << 12) | (b / g);
ans += cnt.get(key) || 0;
}
const c = nums[q + 2];
for (let s = q + 4; s < n; s++) {
const d = nums[s];
const g = gcd(c, d);
const key = ((d / g) << 12) | (c / g);
cnt.set(key, (cnt.get(key) || 0) - 1);
}
}
return ans;
}