题目描述(难度中等)

给定两个整数数组nums1和nums2 ,请你返回根据以下规则形成的三元组的数目（类型1和类型2) :
类型1:三元组(i, j, k) ,如果nums1[i]^2== nums2[j] * nums2[k],其中 0 <= i < nums1.length 且 0= i < k < nums2.length
类型2:三元组(i, j, k) ,如果nums2[i]^2 == nums1[j] * nums1[k],其中 0 <= i < nums2.length 且0= i < k < nums1. length

算法 C++

(哈希表) O(n2 + m2)
1,用两个哈希表分别统计每个数组中,每个数字的平方出现的次数。
2,暴力枚举nums1中的两个元素,求乘积后,答案累加哈希表2中的值;对于nums2同理。时间复杂度维护哈希表的时间复杂度为0(n+m)
·暴力枚举判断的时间复杂度为0(n2 +m2),故总时间复杂度为O(n2 +m2)
空间复杂度需要O(n+m)的额外空间存储哈希表。

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> v1, v2;
    unordered_map<int,int> m1, m2;
    int n, m; // 两个数组的大小
    cin >> n >> m;
    for(int i=0; i<n; i++)
    {
        int a;
        cin >> a;
        v1.push_back(a);
        m1[a*a] += 1;
    }

    for(int i=0; i<m; i++)
    {
        int a;
        cin >> a;
        v2.push_back(a);
        m2[a*a] += 1;
    }
    // 用第一个数组去匹配第二个
    int res = 0;
    for (int i=0; i<v2.size(); i++)
    {
        for (int j=i+1; j<v2.size(); j++)
        {
            res += m1[ v2[i] * v2[j]];
        }
    }
    // 用第二个数组去匹配第一个
    for (int i=0; i<v1.size(); i++)
    {
        for (int j=i+1; j<v1.size(); j++)
        {
            res += m2[ v1[i] * v1[j]];
        }
    }
    cout << res << endl;
    return 0;
}