Easy

题目描述

给你两个长度分别为 n 和 m 的整数数组 nums1 和 nums2，还有一个正整数 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 <= 50
  • 1 <= nums1[i], nums2[j] <= 50
  • 1 <= k <= 50

解题思路

这道题要求找出满足条件的好数对数量，其中好数对 (i, j) 需要满足 nums1[i] 能被 nums2[j] * k 整除。

思路分析：

由于题目的数据规模很小（n, m ≤ 50），我们可以使用暴力枚举的方法。对于每个 nums1[i]，检查它是否能被每个 nums2[j] * k 整除。如果能整除，就增加计数器。

具体步骤：

  1. 初始化计数器 count = 0
  2. 遍历 nums1 的每个元素 nums1[i]
  3. 对于每个 nums1[i]，遍历 nums2 的每个元素 nums2[j]
  4. 检查 nums1[i] % (nums2[j] * k) == 0 是否成立
  5. 如果成立，则 count++
  6. 返回最终的计数结果

这是一个直接的双重循环解法，时间复杂度为 O(n×m)，符合题目要求。由于数据范围较小，这种方法完全可行且是最直观的解决方案。

推荐解法： 暴力枚举法，简单直接且效率足够。

代码实现

class Solution {
public:
    int numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        int count = 0;
        for (int i = 0; i < nums1.size(); i++) {
            for (int j = 0; j < nums2.size(); j++) {
                if (nums1[i] % (nums2[j] * k) == 0) {
                    count++;
                }
            }
        }
        return count;
    }
};

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        count = 0
        for num1 in nums1:
            for num2 in nums2:
                if num1 % (num2 * k) == 0:
                    count += 1
        return count

public class Solution {
    public int NumberOfPairs(int[] nums1, int[] nums2, int k) {
        int count = 0;
        for (int i = 0; i < nums1.Length; i++) {
            for (int j = 0; j < nums2.Length; j++) {
                if (nums1[i] % (nums2[j] * k) == 0) {
                    count++;
                }
            }
        }
        return count;
    }
}

var numberOfPairs = function(nums1, nums2, k) {
    let count = 0;
    for (let i = 0; i < nums1.length; i++) {
        for (let j = 0; j < nums2.length; j++) {
            if (nums1[i] % (nums2[j] * k) === 0) {
                count++;
            }
        }
    }
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n × m)
空间复杂度O(1)

其中 n 是 nums1 的长度，m 是 nums2 的长度。

相关题目