难度：中等
给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。
如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为 优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。
返回 优质数对 的总数。
示例 1：
输入：nums1 = [1,3,4], nums2 = [1,3,4], k = 1
输出：5
解释：
5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。
示例 2：
输入：nums1 = [1,2,4,12], nums2 = [2,4], k = 3
输出：2
解释：
2个优质数对分别是 (3, 0) 和 (3, 1)。
提示：
1 <= n, m <= 10^5
1 <= nums1[i], nums2[j] <= 10^6
1 <= k <= 10^3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
题意比较好理解，难点是数据量特别大，所以需要对nums1和nums2做处理，考虑到nums1和nums2中的数是有可能重复的，可以用map把他们出现的次数记录起来，最后计算优质数对的时候使用对应的数量即可。
并且对nums1提前做了处理，筛选出能够整除k的，可以减少遍历的数量。
function numberOfPairs(nums1: number[], nums2: number[], k: number): number {
nums2 = nums2.map(num => num * k)
nums1 = nums1.filter(num => (num % k == 0))
const n1Map = new Map(), n2Map = new Map()
for(const n of nums1) {
const count = (n1Map.get(n) || 0) + 1
n1Map.set(n, count)
}
for(const n of nums2) {
const count = (n2Map.get(n) || 0) + 1
n2Map.set(n, count)
}
//console.log(nums1)
let ans = 0
for(const n2 of n2Map.keys()) {
for(const n1 of n1Map.keys()) {
if (n1 % n2 == 0) {
ans += n1Map.get(n1) * n2Map.get(n2)
}
}
}
return ans
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
但可惜还是超时了，然后想到合并在nums2中成倍数关系的数，但这样至少也得双重遍历nums2，时间复杂度肯定也超了。或者遍历两遍，但也比较麻烦，索性直接看官方解法。
function numberOfPairs(nums1: number[], nums2: number[], k: number): number {
const count = {};
const count2 = {};
let res = 0, max1 = 0;
for (let num of nums1) {
count[num] = (count[num] || 0) + 1;
max1 = Math.max(max1, num);
}
for (let num of nums2) {
count2[num] = (count2[num] || 0) + 1;
}
for (let a in count2) {
let cnt = count2[a];
for (let b = Number(a) * k; b <= max1; b += Number(a) * k) {
if (b in count) {
res += count[b] * cnt;
}
}
}
return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
思路还是有重叠的，就是统计数字的个数。只不过这里他是取出nums1中的最大值，以此为上限，用nums2中的数去乘以k，然后逐次加倍去判断是否存在于nums1中。
虽然官方解法是过了，但是耗费的时间还是比较久的，六七百ms，但碍于这个庞大的数据量也没啥办法。
时间复杂度：O(n + m + k/v × logm)，其中 n 和 m 分别是数组 nums 1 和 nums 2 的长度，k 是给定的正整数，v 是数组 nums 1 最大值，logm 是「调和级数」求和的结果。