力扣1726同积元组

给你一个由 不同 正整数组成的数组 nums ，请你返回满足 a * b = c * d 的元组 (a, b, c, d)的数量。其中 a、b、c 和 d 都是 nums 中的元素，且 a != b != c != d 。

看到题目描述两两相乘就想到了一个取巧的解法，用类似于笛卡尔积思想将每个数两两相乘的结果保存在一个二维数组中，如下图所示，因为主对角线取不到且以主对角线为对称轴两侧数据相同，所以只需要保存一侧数据即可。

又由题目可知，输出只需要输出答案的个数，不需要数据原本的样子，所以将这些数字保存在一个数组中，进行一次排序
再遍历这个数组，当有相同的数字的时候对数字进行计数，遇到不同的数字结束计数，计算有多少种组合方式，依据公式n*(n+1)/2，将组合数累加得到答案。

class Solution {
    public int tupleSameProduct(int[] nums) {
        int n = nums.length;
        int answer = 0;
        int[] array = new int[n*(n-1)/2];
        int index = 0;
        for(int i=0;i<n-1;++i){
            for(int j=i+1;j<n;++j){
                array[index] = nums[i]*nums[j];
                ++index;
            }
        }
        Arrays.sort(array);
        int temp = 1;
        for(int i=0;i<array.length-1;++i){
            if(array[i]==array[i+1]){
                ++temp;
            }
            else{
                answer+=temp*(temp-1)*4;
                temp = 1;
            }
        }
        return answer;
    }
}

因为这是我独立思考一次通过的题，而且时间空间复杂度还不错，所以记录一下。

本文由 ice 创作，采用 知识共享署名4.0 国际许可协议进行许可。
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名。