Leetcode3164. 优质数对的总数 II

本文主要是介绍Leetcode3164. 优质数对的总数 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Every day a Leetcode

题目来源：3164. 优质数对的总数 II

解法1：统计因子

遍历 nums1，统计所有元素的因子个数，记录到哈希表 cnt 中。

遍历 nums2，那么有 cnt[nums2[i]*k] 个数可以被 nums2[i]*k 整除，加入答案。

代码：

/** @lc app=leetcode.cn id=3164 lang=cpp** [3164] 优质数对的总数 II*/// @lc code=start
class Solution
{
public:long long numberOfPairs(vector<int> &nums1, vector<int> &nums2, int k){unordered_map<int, int> cnt; // 统计因子的出现次数for (int &x : nums1)for (int i = 1; i * i <= x; i++)if (x % i == 0){cnt[i]++;if (i * i < x)cnt[x / i]++;}long long ans = 0LL;for (int &x : nums2)if (cnt.contains(x * k))ans += cnt[x * k];return ans;}
};
// @lc code=end

结果：

在这里插入图片描述

复杂度分析：

时间复杂度：O(n*sqrt(U)+m)，其中 n 是 nums1 的长度，m 是 nums2 的长度，U=max⁡(nums1)。

空间复杂度：O(U)，其中 U=max⁡(nums1)。

解法2：枚举倍数

统计 nums1[i] / k 和 nums2[i] 的出现次数，分别保存到哈希表 cnt1 和 cnt2 中。

设 cnt1 中的最大 key 为 u。枚举 cnt2 中的元素 i，然后枚举 i 的倍数 i、2i、3i…，直到 u，累加这些数在 cnt1 中的 value，乘上 cnt2[i]，加入答案。

代码：

// 枚举倍数class Solution
{
public:long long numberOfPairs(vector<int> &nums1, vector<int> &nums2, int k){unordered_map<int, int> cnt1; // 统计 nums1[i] / k 的出现次数for (int &x : nums1)if (x % k == 0)cnt1[x / k]++;if (cnt1.empty())return 0LL;unordered_map<int, int> cnt2; // 统计nums2[i] 的出现次数for (int &x : nums2)cnt2[x]++;long long ans = 0LL;int u = ranges::max_element(cnt1)->first;for (auto &[i, c] : cnt2){int s = 0;for (int j = i; j <= u; j += i)if (cnt1.contains(j))s += cnt1[j];ans += (long long)s * c;}return ans;}
};