前言

每天和你一起刷 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 := 0for _, 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 := 0for 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 中的值，再相乘，就能得到题目要求的优质数对的总数了。

每天进步一点点，我们明天不见不散~

可以和我刷一辈子的每日一题吗？
一题一题，积累起来就是一辈子。