What is the main pattern in Find the Number of Good Pairs II?

The key pattern is array scanning combined with hash lookup to efficiently count divisible pairs multiplied by k.

Can I use nested loops for this problem?

Nested loops are possible but inefficient; using a hash map avoids timeouts for large arrays.

How do I handle large numbers in nums1 and nums2?

Use integer division carefully and avoid floating point operations when checking divisibility to prevent miscounts.

Is it necessary to preprocess nums2?

Yes, counting occurrences of nums2 elements divided by k in a hash map is essential for efficient lookup.

What is a common failure mode for this problem?

Miscounting arises if you forget to multiply nums2 by k or use floating division, which leads to incorrect total good pairs.

#3164

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

优质数对的总数 II

给你两个整数数组 nums1 和 nums2 ，长度分别为 n 和 m 。同时给你一个正整数 k 。如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为优质数对（ 0 , 0 ）。返回优质数对的总数。示例 1：输入： nums1 = [1,3,…

数组哈希表

题目描述

给你两个整数数组 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⁵
1 <= nums1[i], nums2[j] <= 10⁶
1 <= k <= 10³

lightbulb

解题思路

方法一：哈希表 + 枚举倍数

我们用一个哈希表 $\textit{cnt1}$ 记录数组 $\textit{nums1}$ 中每个数除以 $k$ 的商的出现次数，用一个哈希表 $\textit{cnt2}$ 记录数组 $\textit{nums2}$ 中每个数的出现次数。

接下来，我们枚举数组 $\textit{nums2}$ 中的每个数 $x$ ，对于每个数 $x$ ，我们枚举 $x$ 的倍数 $y$ ，其中 $y$ 的范围是 $[x, \textit{mx}]$ ，其中 $\textit{mx}$ 是 $\textit{cnt1}$ 中的最大键值，然后我们统计 $\textit{cnt1}[y]$ 的和，记为 $s$ ，最后我们将 $s \times v$ 累加到答案中，其中 $v$ 是 $\textit{cnt2}[x]$ 。

时间复杂度 $O(n + m + (M / k) \times \log m)$ ，空间复杂度 $O(n + m)$ ，其中 $n$ 和 $m$ 分别是数组 $\textit{nums1}$ 和 $\textit{nums2}$ 的长度，而 $M$ 是数组 $\textit{nums1}$ 中的最大值。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        cnt1 = Counter(x // k for x in nums1 if x % k == 0)
        if not cnt1:
            return 0
        cnt2 = Counter(nums2)
        ans = 0
        mx = max(cnt1)
        for x, v in cnt2.items():
            s = sum(cnt1[y] for y in range(x, mx + 1, x))
            ans += s * v
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n + m) if using a hash map for counts and scanning each array once. Space complexity is O(m) for storing frequency counts of nums2 divided by k.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect candidate to identify divisible pairs using a combination of iteration and hash lookup.
question_mark
Watch if candidate considers integer division carefully to avoid miscounting.
question_mark
Check whether the solution handles arrays of size up to 10^5 efficiently without nested loops.

warning

常见陷阱

外企场景

error
Attempting nested loops over nums1 and nums2 directly can cause timeouts on large inputs.
error
Using floating point division instead of integer division may result in wrong pair counts.
error
Failing to multiply nums2 elements by k before checking divisibility leads to incorrect results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count good pairs where nums1[i] % (nums2[j] + k) == 0 instead of multiplication by k.
arrow_right_alt
Find maximum number of good pairs instead of total count.
arrow_right_alt
Extend to 3 arrays where a triple (i, j, l) is good if nums1[i] % (nums2[j] * nums3[l] * k) == 0.

help

常见问题

外企场景

继续练习

#3162 优质数对的总数 I #3160 所有球里面不同颜色的数目 #3159 查询数组中元素的出现位置