LeetCode 1726. 同积元组【数组,哈希表】1530

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你一个由 不同 正整数组成的数组 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)
1
2
3
4
5

示例 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
2
3
4
5
6
7

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 10^4
• nums 中的所有元素 互不相同

---

解法 哈希统计

假设当前给定元组 $(a,b,c,d)$ 满足 $a\times b=c\times d$ ，且此时满足 $a<c<d<b$ ，则可以知道该元组可以按照不同顺序组合，组成 $8$ 个不同的元组，且这个 $8$ 个元组均满足题目要求：

• $(a,b,c,d),(a,b,d,c)$ ；
• $(a,b,c,d),(b,a,c,d)$ ；
• $(c,d,a,b),(c,d,b,a)$ ；
• $(d,c,a,b),(d,c,b,a)$ ；

由于数组 $nums$ 由不同正整数组成，这就意味着数组中不存在相同的两个元素。题目要求找两个元素乘积相同的 $4$ 元组，我们可以统计数组中所有不同元素的乘积组合数目，设元素 $a,b$ 的乘积 $a\times b$ 出现的次数为 $\text{cnt}(a\times b)$ ，且满足 $a\ne b$ ，如果此时数组中出现另一对数组 $c,d$ ，满足 $c\times d=a\times b$ ，由于数组中不存在相同的数所以一定满足 $a\ne b，c\ne d$ ，已知 $a\ne b\ne c$ ，则此时一定满足 $a\ne b\ne c\ne d$ 。

根据上述分析，我们只需要在满足乘积相同的 数对 中，任意选择 $2$ 个两不同的数对一定可以满构成 $8$ 个不同的同积元组。根据排列组合可以知道，对于有 $\text{cnt}(a\times b)$ 个数对，则此时可以有 $C^2{}_{\text{cnt}(a\times b)}$ 种不同的数对组合，即此时可以构成的同积元组的数目为: $$\frac{\text{cnt}(a\times b)\times (\text{cnt}(a\times b)-1)}{2}\times 8=\text{cnt}(a\times b)\times (\text{cnt}(a\times b)-1)\times 4$$
根据上述推论，统计数组中所有不同元素的乘积组合数目，然后计算 「相同乘积的数对」可以构成同积元组的数目，并求和即可得到最终的结果。

class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {
        int ans = 0;
        unordered_map<int, int> cnt;
        for (int i = 0; i < nums.size(); i ++)
            for (int j = i + 1; j < nums.size(); j++)
                ++cnt[nums[i] * nums[j]];
        for (auto it : cnt) 
            ans += it.second * (it.second - 1) * 4;   
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

复杂度分析：

• 时间复杂度：$O(n^2)$ ，其中 $n$ 表示数组的长度。求数组中任意两个元素之积以及遍历所有同的两数之积，需要的时间均为 $O(n^2)$ ，因此总的时间复杂度为 $O(n^2)$ 。
• 空间复杂度：$O(n^2)$ ，其中 $n$ 表示数组的长度。统计数组中任意两个元素之积，最多有 $n^2$ 种不同的计算结果，因此需要的空间为 $O(n^2)$ 。