Leetcode 1577 数的平方等于两数乘积的方法数

题目

给你两个整数数组 nums1 和 nums2 ，请你返回根据以下规则形成的三元组的数目（类型 1 和类型 2 ）：

类型 1：三元组 (i, j, k) ，如果$ nums1[i]2 == nums2[j] * nums2[k] 其中 0 <= i < nums1.length 且 0 <= j < k < nums2.length$
类型 2：三元组 (i, j, k) ，如果 $nums2[i]2 == nums1[j] * nums1[k] 其中 0 <= i < nums2.length 且 0 <= j < k < nums1.length$

示例 1：

输入：nums1 = [7,4], nums2 = [5,2,8,9]

输出：1

解释：类型 1：(1,1,2), nums1[1]^2 = nums2[1] * nums2[2] (4^2 = 2 * 8)

示例 2：

输入：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]

示例 3：

输入：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]

示例 4：

输入：nums1 = [4,7,9,11,23], nums2 = [3,5,1024,12,18]

输出：0

解释：不存在符合题目要求的三元组

提示：

1 <= nums1.length, nums2.length <= 1000

1 <= nums1[i], nums2[i] <= 10^5

思路

利用哈希表。

首先对第一个数组的每一个数取平方，然后插入到哈希表中，如果已经存在那么就在原来大小上+1.

然后遍历第二个数组，取两个数的乘积去哈希表里寻找，直接加上哈希表中的数值。

这个数值是有意义的，比如上面给出的示例2，

示例 2：

输入：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里只会得到两个结果是1的值，如果后面遍历后查找哈希表，会只得到“能找到这样的匹配”的结果。但是如果我们让数字有意义，存放nums1中平方得到该值的个数，那么后面遍历时能得到的就不仅仅是能找到这样的匹配了，而是“这样的匹配有n个”，把n加到结果上即可。

注意：

int相乘可能会超过int的范围，这时候要用long，而且要主动转换类型，否则int*int>int范围就会直接报错了。
注意翻转两个数组的顺序再找一遍。

代码与结果

class Solution {

public:

    int numTriplets(vector<int>& nums1, vector<int>& nums2) {

        return hashAndFind(nums1,nums2) + hashAndFind(nums2,nums1);

    }

private:

    int hashAndFind(vector<int>& nums1, vector<int>& nums2){

        int res = 0;

        map<long, int> mp;

        for(auto& num : nums1){

            ++mp[(long)num*num];

        }

        int n = nums2.size();

        for(int i = 0; i< n-1; ++i){

            for(int j=i+1; j<n; ++j){

                res += mp[(long)nums2[i]*nums2[j]];

            }

        }

        return res;

    }

};

结果（大概是没啥人做这个题，所以排名靠前

巴特西

Leetcode 1577 数的平方等于两数乘积的方法数

Leetcode 1577 数的平方等于两数乘积的方法数

题目

思路

代码与结果

最新文章

热门文章