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

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

又由题目可知,输出只需要输出答案的个数,不需要数据原本的样子,所以将这些数字保存在一个数组中,进行一次排序
再遍历这个数组,当有相同的数字的时候对数字进行计数,遇到不同的数字结束计数,计算有多少种组合方式,依据公式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;
    }
}

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

标签: none

添加新评论