【每日一题Day352】LC1726同积元组 | 哈希表+排列组合

简介: 【每日一题Day352】LC1726同积元组 | 哈希表+排列组合

同积元组【LC1726】

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

求出所有二元组的积及其出现次数,假设某个积出现的次数为a,那么其对应的组合数有

image.png

  • 由于题意求的是排列数,即两个二元组顺序可以交换,二元组内部顺序也可以交换,那么最后的排列数还需要乘以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 )

目录
相关文章
|
6月前
【每日一题Day370】LC318最大单词长度乘积 | 哈希表 位运算
【每日一题Day370】LC318最大单词长度乘积 | 哈希表 位运算
51 1
|
6月前
【每日一题Day176】LC2404出现最频繁的偶数元素 | 哈希表
【每日一题Day176】LC2404出现最频繁的偶数元素 | 哈希表
50 0
【每日一题Day176】LC2404出现最频繁的偶数元素 | 哈希表
|
6月前
|
机器学习/深度学习
【每日一题Day120】LC2341数组能形成多少数对 | 哈希表 排序
【每日一题Day120】LC2341数组能形成多少数对 | 哈希表 排序
40 0
|
6月前
【每日一题Day136】LC982按位与为零的三元组 | 哈希表
【每日一题Day136】LC982按位与为零的三元组 | 哈希表
62 0
|
6月前
【每日一题Day163】LC2367算术三元组的数目 | 二分查找 哈希表
【每日一题Day163】LC2367算术三元组的数目 | 二分查找 哈希表
29 0
|
6月前
|
存储
【每日一题Day158】LC2395和相等的子数组 | 哈希表
【每日一题Day158】LC2395和相等的子数组 | 哈希表
31 0
|
6月前
|
存储 人工智能 BI
【每日一题Day147】LC1615最大网络秩 | 枚举 哈希表
【每日一题Day147】LC1615最大网络秩 | 枚举 哈希表
50 0
|
6月前
|
存储
【每日一题Day132】LC23633合并相似的物品 | 哈希表 排序+双指针
【每日一题Day132】LC23633合并相似的物品 | 哈希表 排序+双指针
51 0
|
6月前
【每日一题Day340】LC2251花期内花的数目 | 差分+哈希表+排序 排序+二分查找
【每日一题Day340】LC2251花期内花的数目 | 差分+哈希表+排序 排序+二分查找
38 0
|
6月前
|
算法
【每日一题Day229】LC2352相等行列对 | 哈希
【每日一题Day229】LC2352相等行列对 | 哈希
43 0