LC 100321. 优质数对的总数 II

https://leetcode.cn/problems/find-the-number-of-good-pairs-ii/description/

这题时间复杂度分析上有点意思，调和级数 \(O(m)=1/1 + 1/2 + 1/3 + ... 1/m\) 时间复杂度是 O(lgm) . 

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        from collections import Counter
        cnt1 = Counter([x //k for x in nums1 if x % k == 0])
        if not cnt1: return 0
        U = max(cnt1)

        ans = 0
        for i, c in Counter(nums2).items():
            for j in range(i, U + 1, i): //--- HERE
                ans += cnt1[j] * c
        return ans

调和级数主要是在最后统计部分：