3164. 优质数对的总数 II

Problem: 3164. 优质数对的总数 II

思路

观察本题数据量，可以知道暴力模拟是会超时的，那要怎么求解呢？

首先，两个数组的长度都是$10^5$，每个数据的大小不大于$10^6$，如果我们遍历nums2，并在二重循环里以nums2[j] * k为步伐大小遍历nums2[j] * k，如果答案在nums[1]里有则记录下来（哈希查找时间复杂度$O(1)$），直到nums[1]的最大值为止。第二层遍历的期望时间是比遍历nums1要小的。

但是这样遇到一些测试用例仍然无法通过，仔细看可以发现，题目并没有说明nums1或nums2中的整数不重复，这样对于重复的整数的计算都是冗余的，我们用哈希表维护出现的次数，在找到时改成加上对应出现的次数的乘积即可。

这些测试用例一般都是nums2[j]极小而nums1[i]极大，并且多次重复。如果没有重复，前者就会不可避免地增大，后者相应减小，这样时间复杂度是较低的。

复杂度

• 时间复杂度: $O(n+m+v/k×logm)$，其中n和m分别是数组nums1和nums2的长度，k是给定的正整数，v是数组nums1​最大值，logm是「调和级数」求和的结果。

• 空间复杂度: $O(n + m)$。

Code

class Solution {
    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
        int max = 0;
        long ans = 0;
        Map<Integer, Integer> m = new HashMap<>();
        Map<Integer, Integer> m2 = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            max = max < nums1[i] ? nums1[i] : max;
            m.merge(nums1[i], 1, Integer::sum);
        }
        for (int i = 0; i < nums2.length; i++) {
            m2.merge(nums2[i], 1, Integer::sum);
        }
        for (Map.Entry<Integer, Integer> e : m2.entrySet()) {
            int div = e.getKey() * k;
            for (int j = div; j <= max; j += div) {
                if (m.containsKey(j)) ans += (long)(m.get(j)) * (long)(e.getValue());
            }
        }
        return ans;
    }
}