【每日一题】同积元组

本文主要是介绍【每日一题】同积元组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Tag

【哈希表+组合】【数组】【2023-10-19】

---

题目来源

1726. 同积元组

---

题目解读

在一个由不同正整数组成的数组中找出满足 a * b = c * d 的四元组 (a, b, c, d)，返回这样的四元组的数量。

---

解题思路

方法一：哈希表+组合

我可以先统计所有不同的乘积的数量，如果某一种乘积的数量 m 大于 1，那么可以从中拿出两个乘积（对应 4 个不同的数字）进行组合，每一种四元组内数字交换顺序后可以有 8 种四元组。那么，此时符合条件的四元组有：

$$C_m^2\times 8种$$

最后，返回累加和即可。

实现代码

class Solution {
public:int tupleSameProduct(vector<int>& nums) {unordered_map<int, int> cnts;int n = nums.size();for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {++cnts[nums[i] * nums[j]];}}int res = 0;for (auto [_, cnt] : cnts) {if (cnt >= 2) {res += cnt * (cnt - 1) / 2 * 8;}}return res;}
};

复杂度分析

时间复杂度：$O(n^2)$，$n$ 为数组 nums 的长度。

空间复杂度：$O(k)$，$k$ 为不同的乘积数量。

---

其他语言

python3

class Solution:def tupleSameProduct(self, nums: List[int]) -> int:cnts = defaultdict(int)n = len(nums)for i in range(n):for j in range(i+1, n):cnts[nums[i] * nums[j]] += 1res = 0for _, val in cnts.items():if val >= 2:res += val * (val - 1) // 2 * 8return res

defaultdict 是 Python 中 collections 模块中的一个数据结构，它是 dict 的一个子类。defaultdict 的主要特点是允许你在创建字典时为所有键设置一个默认值，这意味着当你访问不存在的键时，它不会引发 KeyError，而会返回默认值。

在使用 defaultdict 之前通常需要引入库：

from collections import defaultdict

代码中的 defaultdic(int) 表示创建一个 defaultdict，所有不存在的键默认值为0。

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。

这篇关于【每日一题】同积元组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---