今日题目

https://leetcode.com/problems/tuple-with-same-product/description/

思路

本题的核心是找出乘积相同的元组。假设有 n 对数的乘积相同，那么答案就是 $(^2_n) \times 4$。这是因为我们可以从中任意选取两对，组合成一个满足条件的元组。

那么，如何证明这两对数一定是不同的呢？

由于原数组中所有元素互不相同，数组中没有重复数字。因此，若 $a \times b = c \times d$，且 $a \ne c$，则可以推出 $b \ne d$，即两对数必然不同。

方法

因此，只需遍历整个数组，统计所有乘积相同的数对数量即可。

技巧

在 defaultdict、Counter、dict 和 {} 这四种字典类型中，dict 的速度最快。

复杂度

  • 时间复杂度：$O(N ^ 2)$，N 为数组长度。

  • 空间复杂度：$O(N)$，需要存储整个数组。

代码

class Solution:
    def tupleSameProduct(self, nums: List[int]) -> int:
        nums.sort()
        cnt = dict()
        N = len(nums)
        for i in range(N):
            for j in range(i + 1, N):
                tmp = nums[i] * nums[j]
                if tmp not in cnt:
                    cnt[tmp] = 1
                else:
                    cnt[tmp] += 1        
        ans = 0
        for v in cnt.values():
            ans += 4 * (v) * (v - 1)
        
        return ans

image.png