1726 - 同积元组 - 组合数 - 哈希

欢迎关注更多精彩
关注我,学习常用算法与数据结构,一题多解,降维打击。

@[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 中的所有元素 互不相同

Related Topics
  • 组合
  • 哈希
  • 题目剖析&信息挖掘

    此题主要用组合思想,一般些类型题目,需要从小规模数据着手,找到规律总结出公式。

    解题思路

    方法一 哈希+组合数

    分析

    题目说是要找到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
    }
    

    本人码农,希望通过自己的分享,让大家更容易学懂计算机知识。

    在这里插入图片描述