1.题目介绍
2.题解
2.1 方法一：哈希统计
思路与算法
假设当前给定元组 (a,b,c,d)(a,b,c,d)(a,b,c,d) 满足 a×b=c×d，且此时满足 a≠b≠c≠d，则可以知道该元组可以按照不同顺序组合，组成 8 个不同的元组，
且这个8个元组均满足题目要求：
(a,b,c,d),(a,b,d,c)
(b,a,c,d),(b,a,c,d)
(c,d,a,b),(c,d,b,a)
(d,c,a,b),(d,c,b,a)
也就是说，我们只需要统计出乘积 i1*i2 = n（定值） 的二元组(i1,i2)数量，存入\(cnt(a\times b)\)中，然后从中不断选出两个二元组自由组合，\(C_{cnt(a\times b)}^2 \times 8\) 也就是最后的结果。换算成表达式也就是\(\frac{cnt(a\times b)\times(cnt(a\times b)-1)}2\times8\)
所以说现在的问题就是如何统计\(cnt(a\times b)\)
这里很显然的是个统计出现次数的问题，我们理所当然的想到了哈希表统计
只要组织键值对pair(\(a\times b\), 出现次数)即可
代码
class Solution {
public:
int tupleSameProduct(vector<int>& nums) {
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++)
for (int j = i + 1; j < nums.size(); j++){
map[nums[i]*nums[j]]++;
}
int ans = 0;
for (auto &pair : map){
ans += (pair.second) * (pair.second - 1) * 4;
}
return ans;
}
};
复杂度分析
- 时间复杂度：\(o(n^2)\)，双重循环
- 空间复杂度：\(o(n^2)\)，最坏情况下一共有O(n²)种乘积，例如nums全是质数的情况下
2.2 优化？
在官方题解中，我们先用哈希表统计各乘积的出现次数，在最后遍历哈希表计算总个数。这里我们换个思路呢，能否在统计出现次数的时候同时计算总个数呢？这样就可以优化遍历哈希表的循环时间。
答案是肯定可以的，在每次使用一个二元组\(（ nums[i] ,nums[j]）\)计算出一个乘积后，我们便可以直接从哈希表中寻找与其匹配的二元组个数，这里面的每个二元组都能与其构成8个组合，且并不会与之前的组合产生任何重复（固定有一组新的二元组\(（ nums[i] ,nums[j]）\)，直接进行总个数的计算即可 \(ans += 8 * productCount[product];\).
这里若是从计算公式来比较，答案中的\(\frac{cnt(a\times b)\times(cnt(a\times b)-1)}2\times8:\)形式是不是感觉很熟悉？没错，就是等差数列求和公式，\(ans += 8 * productCount[product];\)的计算方式实际上就是将其拆分成了\(8\times (1+2+...+[cnt(a\times b) - 1 ]) = 8 \times \frac{[1 + cnt(a\times b) - 1]\times(cnt(a\times b)-1)}2 = \frac{cnt(a\times b)\times(cnt(a\times b)-1)}2\)
class Solution {
public:
int tupleSameProduct(vector<int>& nums) {
int n = nums.size();
unordered_map<int, int> productCount;
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int product = nums[i] * nums[j];
ans += 8 * productCount[product];
productCount[product]++;
}
}
return ans;
}
};