欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。
@[toc]
题目描述
[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)
示例 3：
输入：nums = [2,3,4,6,8,12]
输出：40
示例 4：
输入：nums = [2,3,5,7]
输出：0
提示：
1 <= nums.length <= 1000
1 <= nums[i] <= 10^4
nums 中的所有元素 互不相同
题目剖析&信息挖掘
此题主要用组合思想，一般些类型题目，需要从小规模数据着手，找到规律总结出公式。
解题思路
方法一 哈希+组合数
分析
题目说是要找到4个数，使得前面2个相乘等于后面2个相乘。很自然想到先把所有俩俩相乘的结果数存储起来，然后去枚举a,b 再去找对应的c,d。
以例1为例进行分析，显然乘积不同的计数结果是相互不干扰的，我们就先统计乘积为12。
根据题意，一共有如下情况：
（2，6），(6，2)，(3，4)，(4，3) 一共4组。
先选择a,b =（2，6），相同数字不可以再选择，故c,d 可以选择(3，4)，(4，3)
同理a,b =（6，2），c,d 可以选择(3，4)，(4，3)
a,b =（3，4），c,d 可以选择（2，6），（6，2）
a,b =（4，3），c,d 可以选择（2，6），（6，2）
从上面可以发现，先选择一个a,b 剩下的组合中除了与a,b数字相同的组合，其他都是可行解。
设cnt[x] = n
则 a,b = c,d = x的组合总数 = n-2 + n-2 … +n-2 (有n个) = (n-2) * n
思路
- 先统计出所有俩俩乘积组合数cnt[x]。
- 对于每个x ，计算出乘积结果为x的组合数。
- 所有结果相加
func tupleSameProduct(nums []int) int {
cntm := make(map[int]int)
// 统计 cntm[x]
// 对于每个x 计算方法数，并加和
sum := 0
return sum
}
注意
- 自己不要和自己乘。
- 题目中已经说明每个数字不相同。
知识点
- 组合
- 哈希
复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)
代码实现
func tupleSameProduct(nums []int) int {
cntm := make(map[int]int)
// 统计 cntm[x]
for _, a := range nums {
for _, b := range nums {
if a==b {continue}
cntm[a*b]++
}
}
// 对于每个x 计算方法数，并加和
sum := 0
for _, v := range cntm {
sum += (v-2) * v
}
return sum
}
本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。
