5508. 数的平方等于两数乘积的方法数 [medium]

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

给你两个整数数组 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

First Try

2020-09-06

看起来题意很长很复杂，其实仔细看就是一个暴力法可解决的问题。直接上三重暴力遍历法，直接超时了。

由于只要求统计数量，不要求具体坐标index，而且只要存在j和k，必然可以选择j和k进行替换实现j<k。因此还对数组进行排序，然后进行提前截断优化，结果还是超时了。

这个时候就只能上字典优化了，从i和j得到目标值target，再查找target是否在剩下的数组中。同时由于不只要求判断target存在，还要统计target的数量，这样只能上collection.Counter才能优化, 然后这道简单的题目终于在超时并优化几次后才搞定了。

class Solution:
    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        
        count = 0 
        intact_c2 = collections.Counter(nums2)
        intact_c1 = collections.Counter(nums1)
        # case 1 
        for i, ni in enumerate(nums1):
            c2 = collections.Counter(intact_c2)
            for j, nj in enumerate(nums2):
                c2[nj] -= 1
                target = ni ** 2 / (nj * 1.0) 
                if target != int(target):
                    continue
                count += c2[int(target)]
                
        # case 2 
        for i, ni in enumerate(nums2):
            c1 = collections.Counter(intact_c1)
            for j, nj in enumerate(nums1):
                c1[nj] -= 1
                target = ni ** 2 / (nj * 1.0) 
                if target != int(target):
                    continue  
                count += c1[int(target)]
                
        return count 

后来看他人的代码，发现并不需要理会j和k之间的顺序，直接统计所有j和k的乘法值，然后判断其中等于i * i的数量即可。在j和k对应数值不同的时候，哪个是j哪个是k只是人为定义。这个思路比我的还要简单许多，现在过于依赖collection这个包了。

class Solution:
    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        
        def counts(nums1, nums2):
            rv = 0 
            counter = collections.defaultdict(int)
            for i in range(len(nums2)):
                for j in range(i + 1, len(nums2)):
                    counter[nums2[i] * nums2[j]] += 1
            for val in nums1:
                rv += counter[ val * val]
            return rv 
    
        rv = 0 
        rv += counts(nums1, nums2)
        rv += counts(nums2, nums1)
        return rv 
            

5508. 数的平方等于两数乘积的方法数 [medium]​

First Try​

5508. 数的平方等于两数乘积的方法数 [medium]

First Try