What is the optimal approach for solving 'Number of Ways Where Square of Number Is Equal to Product of Two Numbers'?

The optimal approach uses hash tables to store squared values of nums1 and nums2, and then scans both arrays to check for valid triplet conditions, reducing the time complexity significantly.

How do hash tables help in solving this problem?

Hash tables store the frequencies of squared values, allowing for fast lookups during the scanning process to check if the product of two numbers equals the square of another number.

What are the main challenges in this problem?

The primary challenges include efficiently calculating squared values, handling large input sizes, and ensuring optimal time complexity using hash lookups during array scanning.

What is the time complexity of the best solution for this problem?

The best solution typically has a time complexity of O(n^2), where n is the length of the arrays, due to the combination checks. However, hashing and precomputation optimize it in practice.

Are there any variations of this problem?

Yes, variations include handling larger datasets, considering a fixed number of triplets, or introducing negative numbers, which adds complexity to the product and square checks.

#1577

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

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

数组哈希表数学双指针

题目描述

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

类型 1：三元组 (i, j, k) ，如果 nums1[i]² == nums2[j] * nums2[k] 其中 0 <= i < nums1.length 且 0 <= j < k < nums2.length
类型 2：三元组 (i, j, k) ，如果 nums2[i]² == 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

lightbulb

解题思路

方法一：哈希表 + 枚举

我们用哈希表 $\textit{cnt1}$ 统计 $\textit{nums1}$ 中每个数对 $(\textit{nums}[j], \textit{nums}[k])$ 出现的次数，其中 $0 \leq j \lt k < m$ ，其中 $m$ 为数组 $\textit{nums1}$ 的长度。用哈希表 $\textit{cnt2}$ 统计 $\textit{nums2}$ 中每个数对 $(\textit{nums}[j], \textit{nums}[k])$ 出现的次数，其中 $0 \leq j \lt k < n$ ，其中 $n$ 为数组 $\textit{nums2}$ 的长度。

接下来，我们枚举数组 $\textit{nums1}$ 中的每个数 $x$ ，计算 $\textit{cnt2}[x^2]$ 的值，即 $\textit{nums2}$ 中有多少对数 $(\textit{nums}[j], \textit{nums}[k])$ 满足 $\textit{nums}[j] \times \textit{nums}[k] = x^2$ 。同理，我们枚举数组 $\textit{nums2}$ 中的每个数 $x$ ，计算 $\textit{cnt1}[x^2]$ 的值，即 $\textit{nums1}$ 中有多少对数 $(\textit{nums}[j], \textit{nums}[k])$ 满足 $\textit{nums}[j] \times \textit{nums}[k] = x^2$ ，最后将两者相加返回即可。

时间复杂度 $O(m^2 + n^2 + m + n)$ ，空间复杂度 $O(m^2 + n^2)$ 。其中 $m$ 和 $n$ 分别为数组 $\textit{nums1}$ 和 $\textit{nums2}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        def count(nums: List[int]) -> Counter:
            cnt = Counter()
            for j in range(len(nums)):
                for k in range(j + 1, len(nums)):
                    cnt[nums[j] * nums[k]] += 1
            return cnt

        def cal(nums: List[int], cnt: Counter) -> int:
            return sum(cnt[x * x] for x in nums)

        cnt1 = count(nums1)
        cnt2 = count(nums2)
        return cal(nums1, cnt2) + cal(nums2, cnt1)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate efficiently use hash tables to store squared values and check combinations?
question_mark
Does the candidate understand how to optimize time complexity with precomputation and hashing?
question_mark
Is the candidate able to adapt array scanning with hash lookups to optimize large input handling?

warning

常见陷阱

外企场景

error
Not leveraging the hash table for fast lookup, leading to a time complexity of O(n^3).
error
Failing to handle edge cases where no valid triplets exist, which could result in incorrect outputs.
error
Misunderstanding the problem constraints, especially regarding the relationship between squared values and product combinations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Adjust the problem to use a fixed number of triplets (e.g., 3 numbers) instead of considering all combinations.
arrow_right_alt
Increase the input size, requiring optimization for larger datasets.
arrow_right_alt
Extend the problem to handle negative numbers, which would require careful handling of square values and product calculations.

help

常见问题

外企场景

继续练习

#1512 好数对的数目 #1679 K 和数对的最大数目 #1442 形成两个异或相等数组的三元组数目