1726. 同积元组
- 题目
- 方法-【哈希】& 题目特征-【出现相同乘积】
题目
题目链接：https://leetcode.cn/problems/tuple-with-same-product/description/
方法-【哈希】& 题目特征-【出现相同乘积】
如果用枚举的方式，那我们需要4个指针代表a、b、c、d，去模拟这个过程，时间复杂度太高了。
题目要找的是 ，即出现相同乘积，需要同时用到统计、查找乘积。
哈希的作用，就是高效统计和查找。
class Solution {
public:
int tupleSameProduct(std::vector<int>& nums) {
int result = 0;
std::unordered_map<int, int> productCount;
for (int i = 0; i < nums.size(); i++)
for (int j = i + 1; j < nums.size(); j++) {
int prod = nums[i] * nums[j];
result += 8 * productCount[prod]; // 每个乘积对可以形成 8 个不同的元组
productCount[prod]++;
}
return result;
}
};当数组 nums = [2, 3, 4, 6] 时，让我们来看一下具体的例子。
首先，我们需要遍历数组 nums，外层循环遍历 a 和 b，内层循环遍历 c 和 d。
- 当 a = 2，b = 3 时，计算乘积 prod = a * b = 2 * 3 = 6。此时，我们在哈希表中统计乘积 6 的出现次数为 0，然后将其加入哈希表并初始化出现次数为 1。
- 继续遍历数组 nums，当 a = 2，b = 4 时，计算乘积 prod = a * b = 2 * 4 = 8。在哈希表中统计乘积 8 的出现次数为 0，将其加入哈希表并初始化出现次数为 1。
- 继续遍历数组 nums，当 a = 2，b = 6 时，计算乘积 prod = a * b = 2 * 6 = 12。在哈希表中统计乘积 12 的出现次数为 0，将其加入哈希表并初始化出现次数为 1。
- 继续遍历数组 nums，当 a = 3，b = 4 时，计算乘积 prod = a * b = 3 * 4 = 12。在哈希表中统计乘积 12 的出现次数为 1，将其累加到结果 result 中：result += 8 * 1 = 8。
- 继续遍历数组 nums，当 a = 3，b = 6 时，计算乘积 prod = a * b = 3 * 6 = 18。在哈希表中统计乘积 18 的出现次数为 0，将其加入哈希表并初始化出现次数为 1。
- 继续遍历数组 nums，当 a = 4，b = 6 时，计算乘积 prod = a * b = 4 * 6 = 24。在哈希表中统计乘积 24 的出现次数为 0，将其加入哈希表并初始化出现次数为 1。
- 最终，返回结果 result = 8。
在这个例子中，我们找到了一个满足条件的元组 (2, 3, 4, 6)，其中 a * b = c * d，且 a、b、c、d 都是 nums 中的元素。并且根据乘积出现的次数，我们将结果 result 累加了 8 次。
每个乘积对可以形成 8 个不同的元组，如 (2,6,3,4)，26 = 34 = 12。
通过换位置，就能得到 8 个同乘积的元组：
(2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3)
(3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2)