1726. 同积元组

🟠   🔖  数组 哈希表 计数  🔗 力扣 LeetCode

题目

Given an array nums of distinct positive integers, return the number of tuples(a, b, c, d)such thata * b = c * d wherea ,b ,c , andd are elements ofnums , anda != b != c != d .

Example 1:

Input: nums = [2,3,4,6]

Output: 8

Explanation: There are 8 valid tuples:

(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)

Example 2:

Input: nums = [1,2,4,5,10]

Output: 16

Explanation: There are 16 valid tuples:

(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)

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 10^4
• All elements in nums are distinct.

题目大意

给你一个由 不同 正整数组成的数组 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 中的所有元素 互不相同

解题思路

1. 计算所有可能的两数乘积：

   • 遍历数组中的每一对不同的元素 (nums[i], nums[j])，其中 i < j。
   • 计算它们的乘积 product = nums[i] * nums[j]。

2. 统计每个乘积出现的次数：

   • 使用一个哈希表（Map）来记录每个乘积出现的次数。
   • 如果某个乘积已经存在于哈希表中，说明之前已经有若干对元素的乘积等于这个值。此时，我们可以根据之前记录的次数来计算新的四元组数量。

3. 计算满足条件的四元组数量：

   • 对于每一对 (nums[i], nums[j])，如果它们的乘积 product 已经在哈希表中出现过 k 次，那么可以形成 8 * k 个新的四元组。
     • 这是因为对于每一对 (nums[i], nums[j])，我们可以与之前记录的 k 对 (a, b) 组合，形成四元组 (a, b, nums[i], nums[j]) 或 (nums[i], nums[j], a, b)，并且每个四元组可以有 4 种排列方式（因为 a * b = nums[i] * nums[j] 可以有多种排列组合）。
   • 因此，每发现一个新的乘积匹配，就增加 8 * k 到结果中。

4. 更新哈希表：

   • 每次计算完一对 (nums[i], nums[j]) 的乘积后，更新哈希表中该乘积的计数。

复杂度分析

• 时间复杂度：O(n^2)，其中 n 是数组的长度，需要遍历所有可能的两数对。
• 空间复杂度：O(n^2)，最坏情况下，所有两数对的乘积都不同，哈希表需要存储 n(n-1)/2 个键值对。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var tupleSameProduct = function (nums) {
	let count = new Map(); // 用于记录每个乘积出现的次数
	let res = 0; // 用于记录满足条件的四元组数量

	for (let i = 0; i < nums.length; i++) {
		for (let j = i + 1; j < nums.length; j++) {
			const product = nums[i] * nums[j]; // 计算当前对的乘积

			if (count.has(product)) {
				// 如果该乘积已经存在，说明之前有若干对元素的乘积等于这个值
				// 每发现一个新的匹配，可以形成 8 * k 个新的四元组
				res += 8 * count.get(product);
			}

			// 更新哈希表中该乘积的计数
			count.set(product, (count.get(product) || 0) + 1);
		}
	}

	return res;
};