2025-01-03：优质数对的总数Ⅱ。用go语言，给定两个整数数组 nums1 和 nums2，分别具有长度 n 和 m，同时

2025-01-03：优质数对的总数Ⅱ。用go语言，给定两个整数数组 nums1 和 nums2，分别具有长度 n 和 m，同时还有一个正整数 k。

如果 nums1 中的元素 nums1[i] 能被 nums2[j] 乘以 k 所整除，我们称这种组合 (i, j) 为 优质数对（其中 0 <= i <= n - 1，0 <= j <= m - 1）。

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

1 <= n, m <= 100000。

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

1 <= k <= 1000。

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

输出：5。

解释：

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

答案2025-01-03：

chatgpt[1]

题目来自leetcode3164。

大体步骤如下：

1. 定义了一个名为numberOfPairs的函数，该函数接收三个参数：两个整数数组nums1和nums2，以及一个正整数k，返回一个int64类型的结果。

2. 在函数内部，创建了两个空的整数计数 map：count和count2，并初始化一个整数max1为 0。

3. 遍历nums1数组中的每个元素，统计每个元素出现的次数，并更新max1为最大的元素值。

4. 遍历nums2数组中的每个元素，同样统计每个元素出现的次数。

5. 使用两层循环，首先遍历count2中的每个元素a和它出现的次数cnt，然后在内部循环中计算可能的优质数对，即符合条件b = a * k且b在count中存在时，增加符合条件的组合数到res中。

6. 最后，返回计算出的总优质数对数量res。

请注意，上述代码的时间复杂度为 O(n + m)，其中 n 代表 nums1 的长度，m 代表 nums2 的长度。

额外空间复杂度主要取决于创建的两个 map 数据结构，为 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;

fnnumber_of_pairs(nums1:Vec<i32>, nums2:Vec<i32>, k:i32)->i64{

letmut count=HashMap::new();

letmut count2=HashMap::new();

letmut 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;

}

letmut res:i64=0;

for(&a,&cnt)in&count2 {

letmut b= a * k;

while b <= max1 {

ifletSome(&count_b)= count.get(&b){

              res += count_b asi64* cnt asi64;

}

          b += a * k;

}

}

  res

}

fnmain(){

letnums1=vec![1,3,4];

letnums2=vec![1,3,4];

letk=1;

letresult=number_of_pairs(nums1, nums2, k);

println!("{}", result);

}

在这里插入图片描述引用链接