原题链接:
https://leetcode.cn/problems/tuple-with-same-product/

解法1:

哈希表记数 + 排列组合求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
    哈希 + 排列组合
    hash记录乘积出现的次数 -> 乘积由两个数相乘构成 -> 出现两次相同的乘积证明有四个数符合题目要求
    -> 出现n次 则只需从n对中任意选两对进行组合即可C(2,n) -> 又因为根据题意四元组内的数顺序不同也是可以算是一种组合 A(2,4) 
*/
class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {
        int n = nums.size();
    
        // 乘积 -> 乘积出现的次数
        unordered_map<int,int>hash;
        for(int i = 0 ; i < n ; i++){
            for(int j = i + 1 ; j < n ; j++){
                hash[nums[i] * nums[j]]++;
            }
        }

        int ans = 0;
        for(auto& [k,v] : hash){
            if(v <= 1){
                continue;
            }
            // v  dsa
            ans += v*(v - 1) / 2  * 8;
       }

       return ans;
    }
};