---

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

• 标签：数组、哈希表、数学、双指针
• 难度：中等

题目链接

• 1577. 数的平方等于两数乘积的方法数 - 力扣

题目大意

描述：给定两个整数数组 $nums1$ 和 $nums2$。

要求：返回满足以下条件的元组数量（$i, j, k$）或（$i, j, k$）：

• 对于 $nums1$：$nums1[i]^2 = nums2[j] \times nums2[k]$，$j \neq k$。
• 对于 $nums2$：$nums2[i]^2 = nums1[j] \times nums1[k]$，$j \neq k$。

返回两种情况的元组总数。

说明：

• $1 \le nums1.length, nums2.length \le 1000$。
• $1 \le nums1[i], nums2[i] \le 10^5$。

示例：

• 示例 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]

解题思路

思路 1：哈希表

1. 核心思想

对于每个数组，计算所有两数乘积的频率。然后遍历另一个数组，计算每个元素的平方，在乘积频率中查找。

注意 $j \neq k$，但对于相同值不同位置的元素视为不同元组。

2. 具体步骤

第 1 步：定义函数 $count(nums_a, nums_b)$：

• 统计 $nums_b$ 中所有两数乘积（$j \le k$）的频率。
• 遍历 $nums_a$，对每个元素 $x$，计算 $x^2$，在乘积频率中查找。

第 2 步：返回 $count(nums1, nums2) + count(nums2, nums1)$。

3. 乘积频率的计算

对于 $j < k$，每个乘积出现一次。
对于 $j == k$，题目要求 $j \neq k$，所以不统计。

freq = {}
for j in range(len(b)):
    for k in range(j + 1, len(b)):
        product = b[j] * b[k]
        freq[product] = freq.get(product, 0) + 1

4. 举例说明

以 $nums1 = [7,4], nums2 = [5,2,8,9]$ 为例：

$nums2$ 的两数积：

• $5\times2=10$, $5\times8=40$, $5\times9=45$, $2\times8=16$, $2\times9=18$, $8\times9=72$。

$nums1$：

• $7^2=49 \notin freq$
• $4^2=16 \in freq$，次数 $1$。

$nums1$ 的两数积：

• $7\times4=28$

$nums2$：

• $5^2=25 \notin freq$
• $2^2=4 \notin freq$
• $8^2=64 \notin freq$
• $9^2=81 \notin freq$

总次数 $= 1$。

思路 1：代码

class Solution:
    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        def count(a, b):
            freq = {}
            for j in range(len(b)):
                for k in range(j + 1, len(b)):
                    product = b[j] * b[k]
                    freq[product] = freq.get(product, 0) + 1
            ans = 0
            for x in a:
                val = x * x
                ans += freq.get(val, 0)
            return ans

        return count(nums1, nums2) + count(nums2, nums1)

思路 1：复杂度分析

• 时间复杂度：$O(n^2 + m^2)$，$n = len(nums1)$，$m = len(nums2)$。
• 空间复杂度：$O(n^2)$ 或 $O(m^2)$，乘积频率表。