Medium

题目描述

给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。另给你一个正整数 k。

如果 nums1[i] 能被 nums2[j] * k 整除（0 <= i <= n - 1，0 <= j <= m - 1），则称数对 (i, j) 为 好数对。

返回好数对的总数。

示例 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

解题思路

这道题需要找到满足 nums1[i] % (nums2[j] * k) == 0 的数对 (i, j) 的数量。

基本思路： 暴力解法是双重循环检查每个数对，时间复杂度为 O(n*m)，在给定约束下会超时。

优化思路：

  1. 首先统计 nums2 中每个值乘以 k 后的出现次数，存储在哈希表中
  2. 对于 nums1 中的每个值 v，我们需要找到有多少个 nums2[j] * k 能整除 v
  3. 关键优化：枚举 v 的所有因子。如果 d 是 v 的因子，且 d 在哈希表中存在，则累加对应的计数

具体步骤：

  • 用哈希表 cnt 统计 nums2[j] * k 的出现次数
  • 对于 nums1 中的每个值 v，枚举其所有因子 d（只需枚举到 √v）
  • 如果因子 d 在 cnt 中存在，累加 cnt[d]
  • 注意：当 d * d == v 时，只计算一次；否则 d 和 v/d 都是因子

这种方法的时间复杂度为 O(n * √max(nums1))，比暴力解法有显著提升。

代码实现

class Solution {
public:
    long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        unordered_map<int, int> cnt;
        for (int x : nums2) {
            cnt[x * k]++;
        }
        
        long long ans = 0;
        for (int v : nums1) {
            for (int d = 1; d * d <= v; d++) {
                if (v % d == 0) {
                    if (cnt.count(d)) {
                        ans += cnt[d];
                    }
                    if (d * d != v && cnt.count(v / d)) {
                        ans += cnt[v / d];
                    }
                }
            }
        }
        
        return ans;
    }
};

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        from collections import Counter
        
        cnt = Counter(x * k for x in nums2)
        
        ans = 0
        for v in nums1:
            d = 1
            while d * d <= v:
                if v % d == 0:
                    if d in cnt:
                        ans += cnt[d]
                    if d * d != v and v // d in cnt:
                        ans += cnt[v // d]
                d += 1
        
        return ans

public class Solution {
    public long NumberOfPairs(int[] nums1, int[] nums2, int k) {
        var cnt = new Dictionary<int, int>();
        foreach (int x in nums2) {
            int key = x * k;
            cnt[key] = cnt.GetValueOrDefault(key, 0) + 1;
        }
        
        long ans = 0;
        foreach (int v in nums1) {
            for (int d = 1; d * d <= v; d++) {
                if (v % d == 0) {
                    if (cnt.ContainsKey(d)) {
                        ans += cnt[d];
                    }
                    if (d * d != v && cnt.ContainsKey(v / d)) {
                        ans += cnt[v / d];
                    }
                }
            }
        }
        
        return ans;
    }
}

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number}
 */
var numberOfPairs = function(nums1, nums2, k) {
    const freq1 = new Map();
    const freq2 = new Map();
    
    for (let num of nums1) {
        freq1.set(num, (freq1.get(num) || 0) + 1);
    }
    
    for (let num of nums2) {
        freq2.set(num * k, (freq2.get(num * k) || 0) + 1);
    }
    
    let count = 0;
    
    for (let [num1, count1] of freq1) {
        for (let [num2k, count2] of freq2) {
            if (num1 % num2k === 0) {
                count += count1 * count2;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m + n × √max(nums1))，其中 m 是 nums2 的长度，n 是 nums1 的长度
空间复杂度O(m)，用于存储哈希表

相关题目