同积元组【LC1726】
给你一个由 不同 正整数组成的数组 nums ，请你返回满足 a * b = c * d 的元组 (a, b, c, d) 的数量。其中 a、b、c 和 d 都是 nums 中的元素，且 a != b != c != d 。思路
求出所有二元组的积及其出现次数，假设某个积出现的次数为a，那么其对应的组合数有
- 由于题意求的是排列数，即两个二元组顺序可以交换，二元组内部顺序也可以交换，那么最后的排列数还需要乘以8
- 实现
使用哈希表存储每个二元组对应的出现次数，在统计次数的同时求出排列数
class Solution { public int tupleSameProduct(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); int n = nums.length, res = 0; for (int i = 0; i < n; i++){ for (int j = i + 1; j < n; j++){ int p = nums[i] * nums[j]; int count = map.getOrDefault(p, 0); res += count * 8; map.put(p, map.getOrDefault(p, count) + 1); } } return res; } }
复杂度
时间复杂度：O(n^2)
空间复杂度：O ( n )
