class Solution {
public:
int tupleSameProduct(vector<int>& nums) {
}
};
1726. 同积元组
给你一个由 不同 正整数组成的数组 nums ，请你返回满足 a * b = c * d 的元组 (a, b, c, d) 的数量。其中 a、b、c 和 d 都是 nums 中的元素，且 a != b != c != d 。
示例 1：
输入：nums = [2,3,4,6] 输出：8 解释：存在 8 个满足题意的元组： (2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3) (3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2)
示例 2：
输入：nums = [1,2,4,5,10] 输出：16 解释：存在 16 个满足题意的元组： (1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2) (2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1) (2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,4,5) (4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)
提示：
1 <= nums.length <= 10001 <= nums[i] <= 104nums 中的所有元素 互不相同原站题解
rust 解法, 执行用时: 76 ms, 内存消耗: 11.1 MB, 提交时间: 2023-10-19 09:04:50
use std::collections::HashMap;
impl Solution {
pub fn tuple_same_product(nums: Vec<i32>) -> i32 {
let mut counter = HashMap::new();
for i in 0..nums.len() {
for j in (i + 1)..nums.len() {
*counter.entry(nums[i] * nums[j]).or_insert(0) += 1;
}
}
counter.values().map(|c| c * (c - 1) * 4).sum()
}
}
golang 解法, 执行用时: 144 ms, 内存消耗: 30.4 MB, 提交时间: 2023-05-10 10:22:20
func tupleSameProduct(nums []int) int {
tmp := make(map[int]int)
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
tmp[nums[i]*nums[j]]++
}
}
result := 0
for _, v := range tmp {
if v <= 1 {
continue
}
result += (v - 1) * v / 2 * 8
}
return result
}
java 解法, 执行用时: 173 ms, 内存消耗: 61.2 MB, 提交时间: 2023-05-10 10:21:16
class Solution {
public int tupleSameProduct(int[] nums) {
Map<Integer,Integer> map=new HashMap<>();
int len=nums.length;
int count=0;
for(int i=0;i<len-1;i++){
for(int j=i+1;j<len;j++){
int key=nums[i]*nums[j];
int val=map.getOrDefault(key,0);
map.put(key,val+1);
count+=val;
}
}
return count<<3;
}
}
python3 解法, 执行用时: 632 ms, 内存消耗: 44.3 MB, 提交时间: 2023-05-10 10:20:44
class Solution:
def tupleSameProduct(self, nums: List[int]) -> int:
cnt = defaultdict(int)
ans = 0
for i in range(len(nums)):
for j in range(i+1, len(nums)):
product = nums[i] * nums[j]
cnt[product] += 1
if cnt[product] > 1: ans += (cnt[product] - 1) * 8
return ans
cpp 解法, 执行用时: 400 ms, 内存消耗: 79.6 MB, 提交时间: 2023-05-10 10:20:05
class Solution {
public:
int tupleSameProduct(vector<int>& nums) {
int n = nums.size();
unordered_map<int, int> mp;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
mp[nums[i] * nums[j]]++;
}
}
int ret = 0;
// 遍历哈希表
for(auto c : mp) {
ret += c.second * (c.second - 1) / 2;
}
return ret * 8;
}
};