前言
每天和你一起刷 LeetCode 每日一题~
LeetCode 启动！
题目：优质数对的总数 I
代码与解题思路
简单题先暴力~
直接对着题意模拟即可，力扣上只要是标着简单标签的题目，不用犹豫，直接对他使用暴力吧！
func numberOfPairs(nums1 []int, nums2 []int, k int) (ans int) {
// 简单题先暴力
for _, v1 := range nums1 {
for _, v2 := range nums2 {
if v1 % (v2*k) == 0 {
ans++
}
}
}
return ans
}
除了暴力，有没有更好的解法呢？
这是一道力扣周赛的题目，除了简单版本，还有加强了数据的版本，如果没法使用 O（n * m）的复杂度，如何实现线性的题解？
来看代码
func numberOfPairs(nums1 []int, nums2 []int, k int) (ans int64) {
// 同样的题目，加强的数据范围
cnt1 := map[int]int{}
mx := 0
for _, v := range nums1 { // 给每一个能整除 k 的值计数
if v%k == 0 {
cnt1[v/k]++
mx = max(mx, v/k) // 记录 nums1 中能整除 k 的最大数
}
}
if len(cnt1) == 0 { // 没有能整除 k 的数
return 0
}
cnt2 := map[int]int{}
for _, v := range nums2 { // 给 nums2 中的每一种数字计数
cnt2[v]++
}
// 为什么可以通过枚举倍数来做？
// 举例：3 % 1 == 0，3 为什么能整除 1，因为 3 是 1 的倍数
// 1 的倍数有 1、2、3 等等，所以他能被 1、2、3 整除
// 这也就意味着，我们只需要枚举一个数的倍数，就能得到所有能整除他的值。
// 也就是我们将 nums2 中的值的所有倍数枚举一遍，和 nums1 中能整除 k 的值进行比较
// 然后根据他们的数量相乘计算数对的数量，就能得到题目要求的结果
for k, v := range cnt2 { // 枚举 nums2 中的每一个数字和他们的数量
cnt := 0
for t := k; t <= mx; t += k { // 枚举这每一个数字的倍数
cnt += cnt1[t] // 如果和 nums1 中的值能对应，就记录
}
ans += int64(cnt*v) // nums1 中该值的数量 * nums2 中该值的数量 = 该值能整除的优质数对数
}
return ans
}
解题逻辑：
1、给 nums1 每一个能整除 k 的值计数
2、记录 nums2 中每一个种数字的个数
3、枚举 nums2 中每一种数字的倍数，并累加解得优质数对的总数
核心问题：（注释也有简略提到）
为什么可以这么做？或者说，为什么可以通过枚举 nums2 中每一种数字的倍数来解得题目要求的优质数对的总数？
题目中说： nums1[i] 可以被 nums2[j] * k 整除，就是一个优质的数对，也就是说可以转换成：nums[i] / k 可以被 nums2[j] 整除
举个例子：3 可以被 1 整除，3 为什么可以被 1 整除？因为 3 是 1 被倍数。1 的倍数有 1、2、3 . . .，所以 1 能被 1，2，3 整除，也就说，只要我们枚举 1 的倍数，就能找到什么 1 能被什么值整除了
我们将 nums1 中能整除的值计数，nums2 中的值计数，通过枚举 nums2 中值的倍数，找到对应能的 nums1 中的值，再相乘，就能得到题目要求的优质数对的总数了。