请看示例,可发现规律:乘积相同的两个数对,存在8种排列,满足同积元组的要求。于是有结论:乘积相同的两个数对,对答案的贡献是ans=ans+8
.
如上所述,我们需要先知道数对的乘积,才知道乘积相同的数对个数。请看如下步骤:遍历数组nums的数对组合,求数对的乘积,之所以遍历数对组合是根据题意避免重复计算。统计乘积相同的数对数目(哈希表存储{数对乘积, 数对数目}),即可计算对答案的贡献,求出答案。
设n个乘积相同的数对,有 C n 2 C_n^2 Cn2种组合, C n 2 = n × ( n − 1 ) 2 C^2_n=\dfrac{n\times(n-1)}{2} Cn2=2n×(n−1),对答案的贡献: C n 2 × 8 = n × ( n − 1 ) 2 × 8 C^2_n \times 8=\dfrac{n\times(n-1)}{2}\times 8 Cn2×8=2n×(n−1)×8
class Solution {
public:
int tupleSameProduct(vector<int>& nums) {
unordered_map<int, int> mp;
int ans = 0;
for (int i = 0; i < nums.size(); i ++) {
for (int j = i + 1; j < nums.size(); j ++) {
mp[nums[i] * nums[j]] ++; // 统计组合数的乘积
}
}
for (unordered_map<int, int>::iterator it = mp.begin(); it != mp.end(); it ++) {
ans += (*it).second * ((*it).second - 1) / 2 * 8;
}
return ans;
}
};
时间复杂度 O ( n 2 ) O(n^2) O(n2):统计组合数的乘积的时间复杂度 O ( n 2 ) O(n^2) O(n2)。
空间复杂度 O ( n 2 ) O(n^2) O(n2):数对乘积全然不同时,最坏空间复杂度 O ( n 2 ) O(n^2) O(n2)。