Tuples with Same Product
给一个数组, 里面的数字不同, 求多少种a*b=c*d, abcd都是数组的数字, 但是不相同.
算下乘积的频率即可, 答案是n*(n-1),从频率中任意选2个的个数, 然后再乘以4, 4种互换可能.
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> f = new HashMap<>(); for(int i = 0; i < nums.length; i++) { for(int j = i + 1; j < nums.length; j++) { f.put(nums[i] * nums[j], f.getOrDefault(nums[i] * nums[j], 0) + 1); } } int res = 0; for(Map.Entry<Integer, Integer> m : f.entrySet()){ int n = m.getValue(); res += (n) * (n - 1) * 4; } return res; } } |