LC.P1726[同积元组]

方法一:数学+哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int tupleSameProduct(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 1; i < nums.length; ++i) {
for (int j = 0; j < i; ++j) {
int x = nums[i] * nums[j];
map.merge(x, 1, Integer::sum);
}
}
int ans = 0;
for (int v : map.values()) {
ans += v * (v - 1) / 2;
}
return ans << 3;
}
}
  • 时间复杂度:$O(n^2)$
  • 空间复杂度:$O(n^2)$