Back to Leetcode

Readme

Math/3164.Find-the-Number-of-Good-Pairs-II/Readme.md

latest505 B
Original Source

3164.Find-the-Number-of-Good-Pairs-II

首先,我们必然将nums1里不能被k整除的去除掉。

接下来,我们就是要寻找有多少个pair,使得nums1的元素能被nums2里的元素整除。看上去似乎没有比o(MN)更好的方法了。但是我们可以换一个角度就豁然开朗。我们可以枚举nums1[i]的约数,只需要sqrt(V)次。对于每个约数我们只需要在hash表里查看是否存在这样的nums2元素即可。这样时间复杂度就是N*sqrt(V).