力扣(LeetCode)1726. 同积元组(C++)

哈希表

请看示例，可发现规律：乘积相同的两个数对，存在8种排列，满足同积元组的要求。于是有结论：乘积相同的两个数对，对答案的贡献是ans=ans+8.

如上所述，我们需要先知道数对的乘积，才知道乘积相同的数对个数。请看如下步骤：遍历数组nums的数对组合，求数对的乘积，之所以遍历数对组合是根据题意避免重复计算。统计乘积相同的数对数目(哈希表存储{数对乘积, 数对数目})，即可计算对答案的贡献，求出答案。

设n个乘积相同的数对，有$C_n^2$种组合，$C_n^2=\frac{n\times (n-1)}{2}$，对答案的贡献：$C_n^2\times 8=\frac{n\times (n-1)}{2}\times 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间复杂度 $O(n^2)$：统计组合数的乘积的时间复杂度$O(n^2)$。

空间复杂度 $O(n^2)$：数对乘积全然不同时，最坏空间复杂度$O(n^2)$。

致语

• 理解思路很重要。
• 请读者放心留言，可以是疑惑的点，或者讨论！！墨染看到会回复的。