leetcode_1726 同积元组

1. 题意

给一个不重复的整数数组a，找出满足a1 * a2 = a3 * a4的四元组个数。
同积元组

2. 题解

组合数学+哈希计数。

循环求出任意两个数之积的次数(v,cnt)。

最终的结果
$$ans=8\sum _{i=0}^{sz}{C}_{v_i}^2$$

class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {


        unordered_map<int,int> um;

        int sz = nums.size();
        for (int i = 0; i < sz - 1; ++i) {
            for (int j = i + 1;j < sz; ++j){
                int v = nums[i] * nums[j];
                um[v]++;
            }
        }
        int ans = 0;
        for (auto &[k,v]: um)
                ans += v * (v - 1)/2 * 8;

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21