Skip to main content

1726. Tuple with Same Product

解题思路​

这道题要求找到数组 nums 中所有满足 a * b = c * d 的四元组 (a, b, c, d)，其中 a, b, c, d 互不相等。由于 nums 是互不相同的正整数，我们可以利用哈希表（dict）来存储所有可能的乘积及其对应的数对数量，从而高效地找到符合条件的四元组。

解题步骤：​

  1. 枚举所有可能的数对：对于数组 nums 的任意两个数 (nums[i], nums[j])，计算它们的乘积 p = nums[i] * nums[j]。
  2. 使用哈希表存储乘积及其对应的数对数量：若 p 之前已经出现过，说明存在其他数对 (c, d) 使得 c * d = p，可以组合成符合条件的四元组。
  3. 计算符合条件的四元组个数：
    • 对于每个乘积 p，如果它出现 count 次，则可以从 count 个数对中选择两个数对 (a, b) 和 (c, d) 进行排列。
    • 每一组 (a, b), (c, d) 可以形成 8 个四元组（考虑顺序）。
    • 因此，最终的四元组个数可以通过公式 count * (count - 1) / 2 * 8 计算。

Python 代码实现：​

from collections import defaultdict
from typing import List

class Solution:
    def tupleSameProduct(self, nums: List[int]) -> int:
        product_count = defaultdict(int)  # 存储乘积出现的次数
        n = len(nums)
        result = 0
        
        # 计算所有数对的乘积并记录出现次数
        for i in range(n):
            for j in range(i + 1, n):
                product = nums[i] * nums[j]
                product_count[product] += 1
        
        # 计算四元组数量
        for count in product_count.values():
            if count > 1:
                result += (count * (count - 1) // 2) * 8  # 计算所有可能的四元组
        
        return result

复杂度分析：​

  • 时间复杂度：O(N²)，其中 N 是 nums 的长度，因为我们需要枚举所有可能的 (a, b) 数对。
  • 空间复杂度：O(N²)，最坏情况下，每个数对的乘积都不同，我们需要存储 O(N²) 个键值对。

示例：​

输入：​

nums = [2, 3, 4, 6]
solution = Solution()
print(solution.tupleSameProduct(nums))

计算过程：​

  • 所有可能的乘积： 
    2*3=6,  2*4=8,  2*6=12
    3*4=12, 3*6=18
    4*6=24
  • 乘积 12 出现 2 次，可以形成 8 个四元组 (2,6,3,4) 和 (3,4,2,6)。

输出：​

8

总结：​

  1. 通过枚举数对来计算乘积，并使用哈希表存储乘积频率。
  2. 通过组合计数计算符合条件的四元组数目。
  3. 时间复杂度为 O(N²)，适用于 nums 长度较小的情况。

这样，我们就能高效地找到所有符合 a * b = c * d 的四元组了！ 🚀