力扣1726. 同积元组

本文主要是介绍力扣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 <= 1000
• 1 <= nums[i] <= 104
• nums 中的所有元素 互不相同

思路：

这个题目的大概的意思就是找四个不同的数，这四个数可以组成a*b=c*d的数量.

因为题目给的数组的长度是1000,直接暴力找4个数肯定是超时。

我们可以用一个数组num1把等式左边存下来，也就是把nums数组中任意两个数的乘积存下来,同时用一个map存下任意两个数的乘积的个数，时间复杂度是N^2。

接下来遍历num1,对于每两个数的乘积看是否还有另外两个数的乘积是一样的。记录数量就ok了。

首先，因为这四个数互不相等，我们应该先对nums进行去重，也就是将相同的元素去掉，这样对答案没有影响。

另外我们要考虑的就是，在遍历num1的时候，因为map记录了一次num1[i]本身，所以我们应该看此时的map[num1[i]]是否大于等于2，如果大于等于2，说明除了num1[i]还可以找到map[num1[i]]-1个两元乘积等于num1[i]，此时答案ans+=map[num1[i]]-1,又因为此时的num1[i]已经作为等式左边计算过了，需要map[num1[i]]--。

比如 nums=[1,2,4,5,10]

那么任意两不同数之积num1=[2,4,5,10,8,10,20,20,40,50],同时用mp记录num1[i]的数量。

这里我们可以理解为每一个num1[i]，都是等式的左边的二元数之积。

mp[10]=2,mp[20]=2（只看大于等于2的)

此时遍历num1，假如map[num1[i]]大于等于2，说明可以对于左边的num1[i]，可以找到右边的二元数之积与之相等，然后再消除num[i]对后面元素作为等式左边值的影响，mp[num1[i]]--，不做么做的话，同一个四元积就重复了。

代码：

#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:int tupleSameProduct(vector<int>& nums) {vector<int> num1;sort(nums.begin(), nums.end());nums.erase(unique(nums.begin(), nums.end()), nums.end());//排序去重map<int, int> mp;for (int i = 0; i < nums.size(); i++) {for (int j = i + 1; j < nums.size(); j++) {num1.push_back(nums[i] * nums[j]);mp[nums[i] * nums[j]]++;//映射二元积的数量}}       int ans = 0;for (int i = 0; i < num1.size(); i++) {if (mp[num1[i]] >= 2) {ans += mp[num1[i]] - 1;mp[num1[i]]--;//消除影响}}return ans * 8//每一个四积元组的顺序可以有八种}
};

这篇关于力扣1726. 同积元组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---