同积元组【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 )