Medium

题目描述

给定一个由不同正整数组成的数组 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,5,4)
(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)

约束条件：

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

提示：

  • 注意所有整数都是不同的。这意味着每次形成乘积时，必须由两个唯一整数组成。
  • 计算每个两个不同数字乘积的频率，然后计算形成的排列。

解题思路

这道题的核心思路是哈希表计数 + 组合数学。

首先分析题目要求：找出满足 a * b = c * d 且四个数都不同的元组数量。关键观察是，如果两对数的乘积相等，那么我们就找到了可能的解。

解题步骤：

  1. 枚举所有数对乘积：遍历数组中所有可能的数对 (i, j)，计算它们的乘积，并用哈希表记录每个乘积出现的次数。

  2. 计算组合方案：对于每个出现次数为 count 的乘积，我们有 count 个不同的数对能产生这个乘积。从中选择2个数对就能组成一个满足条件的四元组。根据组合数学，方案数为 C(count, 2) = count * (count - 1) / 2。

  3. 计算排列数：每选定两个数对后，比如 (a,b) 和 (c,d)，可以形成 8 种不同的元组排列：

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

因此，每一对数对贡献 8 个元组。最终答案就是所有乘积的 count * (count - 1) / 2 * 8。

时间复杂度为 O(n²)，空间复杂度为 O(n²)。

代码实现

class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {
        unordered_map<int, int> productCount;
        int n = nums.size();
        
        // 计算所有数对的乘积
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int product = nums[i] * nums[j];
                productCount[product]++;
            }
        }
        
        int result = 0;
        // 对于每个乘积，计算能形成的元组数量
        for (auto& pair : productCount) {
            int count = pair.second;
            if (count >= 2) {
                // C(count, 2) * 8 = count * (count - 1) / 2 * 8 = count * (count - 1) * 4
                result += count * (count - 1) * 4;
            }
        }
        
        return result;
    }
};

class Solution:
    def tupleSameProduct(self, nums: List[int]) -> int:
        from collections import defaultdict
        
        product_count = defaultdict(int)
        n = len(nums)
        
        # 计算所有数对的乘积
        for i in range(n):
            for j in range(i + 1, n):
                product = nums[i] * nums[j]
                product_count[product] += 1
        
        result = 0
        # 对于每个乘积，计算能形成的元组数量
        for count in product_count.values():
            if count >= 2:
                # C(count, 2) * 8 = count * (count - 1) / 2 * 8 = count * (count - 1) * 4
                result += count * (count - 1) * 4
        
        return result

public class Solution {
    public int TupleSameProduct(int[] nums) {
        Dictionary<int, int> productCount = new Dictionary<int, int>();
        int n = nums.Length;
        
        // 计算所有数对的乘积
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int product = nums[i] * nums[j];
                if (productCount.ContainsKey(product)) {
                    productCount[product]++;
                } else {
                    productCount[product] = 1;
                }
            }
        }
        
        int result = 0;
        // 对于每个乘积，计算能形成的元组数量
        foreach (var pair in productCount) {
            int count = pair.Value;
            if (count >= 2) {
                // C(count, 2) * 8 = count * (count - 1) / 2 * 8 = count * (count - 1) * 4
                result += count * (count - 1) * 4;
            }
        }
        
        return result;
    }
}

var tupleSameProduct = function(nums) {
    const productCount = new Map();
    const n = nums.length;
    
    // 计算所有数对的乘积
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const product = nums[i] * nums[j];
            productCount.set(product, (productCount.get(product) || 0) + 1);
        }
    }
    
    let result = 0;
    // 对于每个乘积，计算能形成的元组数量
    for (const count of productCount.values()) {
        if (count >= 2) {
            // C(count, 2) * 8 = count * (count - 1) / 2 * 8 = count * (count - 1) * 4
            result += count * (count - 1) * 4;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)需要遍历所有可能的数对组合
空间复杂度O(n²)哈希表最多存储 O(n²) 个不同的乘积