同积元组
难度:
标签:
题目描述
Given an array nums of distinct positive integers, return the number of tuples (a, b, c, d) such that a * b = c * d where a, b, c, and d are elements of nums, and a != 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 <= 10001 <= nums[i] <= 104- All elements in
numsare distinct.
代码结果
运行时间: 277 ms, 内存: 54.0 MB
/*
* 思路：
* 1. 使用Map来存储每个乘积以及对应的数对的个数。
* 2. 使用流处理对数组进行两两组合，并计算其乘积。
* 3. 如果Map中已经存在该乘积，则计数增加。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int tupleSameProduct(int[] nums) {
Map<Integer, Integer> productCount = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
int product = nums[i] * nums[j];
productCount.put(product, productCount.getOrDefault(product, 0) + 1);
}
}
return productCount.values().stream()
.mapToInt(count -> count * (count - 1) * 4)
.sum();
}
}
解释
方法:
这个题解利用了哈希表来统计每一对乘积的出现次数。首先，对数组进行排序，然后使用两层循环遍历所有可能的两数乘积，并将这些乘积存储到一个列表中。之后，利用Counter统计列表中每个乘积出现的次数。对于每个乘积出现次数大于1的情况，计算可以由这些乘积形成的合法元组的数量，使用组合数的计算方法 C(n, 2) = n*(n-1)/2 来计算能够从中选取两对数字的方式数。最后，由于每个四元组可以以8种不同的方式排列（因为每对乘积可以交换位置，且两对乘积间也可以交换），所以将结果乘以8返回。
时间复杂度:
O(n^2)
空间复杂度:
O(n^2)
代码细节讲解
🦆
为什么在计算乘积时选择对数组进行排序？这一步是否对算法的正确性或效率有特定的影响？
▷🦆
在实现中，使用Counter统计乘积的出现次数后，只有当一个乘积的出现次数大于1时才进一步计算元组数。请问为什么乘积出现一次的情况不需要被计算？
▷🦆
题解中提到`每个四元组可以以8种不同的方式排列`，能否详细解释这8种排列是如何得到的？
▷