leetcode-1577

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+类型2)个数

代码及解析：

题目意思就是其中一个数组中的数的平方等于另一个数组里任意两个数乘积的个数

代码中我用到了hash记录乘积值，原因是数组访问速度慢，容易超时(结果的确超时了)

class Solution:
    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        num11=[] #nums1的平方数
        num22=[] #nums2的平方数
        num111={}#nums1的任意两元素的乘积，key为乘积值，value为内部元素乘积相等的次数
        num222={}#num2的任意两元素的乘积，key为乘积值，value为内部元素乘积相等的次数
        res=0 #记录次数
        for i in nums1:
            num11.append(i**2)
        for j in nums2:
            num22.append(j**2)
        for i  in range(len(nums1)):
            for j in range(i+1,len(nums1)):
                num111[nums1[i]*nums1[j]]=num111.get(nums1[i]*nums1[j],0)+1
        for i  in range(len(nums2)):
            for j in range(i+1,len(nums2)):
                num222[nums2[i]*nums2[j]]=num222.get(nums2[i]*nums2[j],0)+1
        for i in range(len(num11)):
            if num11[i] in num222.keys():
                res+=num222[num11[i]]
        for i in range(len(num22)):
            if num22[i] in num111.keys():
                res+=num111[num22[i]]
        return res