2025-01-01：优质数对的总数Ⅰ。用 go 语言，给定两个整数数组 nums1 和 nums2，分别长度为 n 和 m，以及一个正整数 k。如果 nums1 数组中的元素 nums1[i] 能被

作者：福大大架构师每日一题

2025-01-01
北京
本文字数：1531 字
阅读完需：约 5 分钟

2025-01-01：优质数对的总数Ⅰ。用 go 语言，给定两个整数数组 nums1 和 nums2，分别长度为 n 和 m，以及一个正整数 k。

如果 nums1 数组中的元素 nums1[i] 能被 nums2 数组中的元素 nums2[j] 乘以 k 除尽，则称 (i, j) 为一个优质数对（其中 0 <= i <= n - 1，0 <= j <= m - 1）。

请计算并返回所有优质数对的数量。

1 <= n, m <= 50。

1 <= nums1[i], nums2[j] <= 50。

1 <= k <= 50。

输入：nums1 = [1,3,4], nums2 = [1,3,4], k = 1。

输出：5。

解释：

5 个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。

答案 2025-01-01：

chatgpt

题目来自 leetcode3162。

大体步骤如下：

1.创建两个空的 map 数据结构 count 和 count2 来分别记录 nums1 和 nums2 中出现的数字及其出现次数。

2.初始化变量 max1 为 0，用于记录 nums1 中的最大值。

3.遍历 nums1 数组，对 count 中相应数字的出现次数进行统计，同时更新 max1 的值为 nums1 中的最大数字。

4.遍历 nums2 数组，对 count2 中相应数字的出现次数进行统计。

5.初始化变量 res 为 0，用于记录符合条件的优质数对数量。

6.遍历 count2 中的数字 a 及其出现次数 cnt，然后从 ak 开始到 max1，每次以 ak 增加的步长遍历 b。

7.在遍历过程中，若 count 中存在 b 这个数字，则将 count[b] 和 count2[a] 的乘积加到 res 中。

8.返回最终的 res 值作为优质数对的总数。

总的时间复杂度：

假设 nums1 的长度为 n，nums2 的长度为 m，k 的值为常数，代码中的主要循环是两个 for 循环，第一个 for 循环是遍历 count2 中的元素，第二个 for 循环是根据 k 和 a 的值计算另一个数组中的元素并检查是否存在。因此，总的时间复杂度为 O(n*m)。

总的额外空间复杂度：

在代码中使用了两个 map 数据结构 count 和 count2 用于存储数字及其出现次数，再加上少量的变量空间，因此总的额外空间复杂度为 O(n + m)。

Go 完整代码如下：

package main
import (  "fmt")
func numberOfPairs(nums1 []int, nums2 []int, k int) int64 {  count := make(map[int]int)  count2 := make(map[int]int)  max1 := 0  for _, num := range nums1 {    count[num]++    if num > max1 {      max1 = num    }  }  for _, num := range nums2 {    count2[num]++  }  var res int64  for a, cnt := range count2 {    for b := a * k; b <= max1; b += a * k {      if _, ok := count[b]; ok {        res += int64(count[b] * cnt)      }    }  }  return res}
func main() {  nums1 := []int{1, 3, 4}  nums2 := []int{1, 3, 4}  k := 1  result := numberOfPairs(nums1, nums2, k)  fmt.Println(result)}

复制代码

Rust 完整代码如下：

use std::collections::HashMap;
fn number_of_pairs(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> i64 {    let mut count = HashMap::new();    let mut count2 = HashMap::new();    let mut max1 = 0;
    for &num in &nums1 {        *count.entry(num).or_insert(0) += 1;        if num > max1 {            max1 = num;        }    }
    for &num in &nums2 {        *count2.entry(num).or_insert(0) += 1;    }
    let mut res: i64 = 0;
    for (&a, &cnt) in &count2 {        let mut b = a * k;        while b <= max1 {            if let Some(&count_b) = count.get(&b) {                res += count_b as i64 * cnt as i64;            }            b += a * k;        }    }        res}
fn main() {    let nums1 = vec![1, 3, 4];    let nums2 = vec![1, 3, 4];    let k = 1;    let result = number_of_pairs(nums1, nums2, k);    println!("{}", result);}