题目描述

https://leetcode.com/problems/number-of-ways-where-square-of-number-is-equal-to-product-of-two-numbers/

样例

输入：nums1 = [7,4], nums2 = [5,2,8,9]
输出：1
解释：类型 1：(1,1,2), nums1[1]^2 = nums2[1] * nums2[2] (4^2 = 2 * 8)

输入：nums1 = [1,1], nums2 = [1,1,1]
输出：9
解释：所有三元组都符合题目要求，因为 1^2 = 1 * 1
类型 1：(0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2), nums1[i]^2 = nums2[j] * nums2[k]
类型 2：(0,0,1), (1,0,1), (2,0,1), nums2[i]^2 = nums1[j] * nums1[k]

输入：nums1 = [7,7,8,3], nums2 = [1,2,9,7]
输出：2
解释：有两个符合题目要求的三元组
类型 1：(3,0,2), nums1[3]^2 = nums2[0] * nums2[2]
类型 2：(3,0,1), nums2[3]^2 = nums1[0] * nums1[1]

算法1

哈希表

• 两数之和 的变形
• 先用哈希表存储 a 数组中每一个元素的平方
• 再两两遍历 b 数组，看看乘积在不在哈希表里
• 注意两个int乘可能会爆，所以用ll

时间复杂度

O(n^2)

参考文献

y总视频

C++ 代码

typedef long long LL;

class Solution {
public:
    int work(vector<int>& a, vector<int>& b){
        int res = 0;
        unordered_map<LL,int> hash;
        for(int x: a) hash[(LL)x * x]++;
        for(int j = 0; j < b.size(); j++)
            for(int k = j + 1; k < b.size(); k++)
                res += hash[(LL)b[j] * b[k]];
        return res;
    }
    int numTriplets(vector<int>& nums1, vector<int>& nums2) {
        return work(nums1,nums2) + work(nums2,nums1);
    }
};