题目描述:
给你两个整数数组 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
示例 :
输入:nums1 = [7,4], nums2 = [5,2,8,9]
输出:1
提示:
- 1 <= nums1.length, nums2.length <= 1000
- 1 <= nums1[i], nums2[i] <= 105
哈希表存储两个数组的平方,然后两次遍历另一个数组的两元素乘积。
class Solution: def numTriplets(self, nums1: List[int], nums2: List[int]) -> int: nums12pos = Counter([x**2 for x in nums1]) nums22pos = Counter([x**2 for x in nums2]) res = 0 for i in range(len(nums2)): for j in range(i + 1, len(nums2)): res += nums12pos[nums2[i] * nums2[j]] for i in range(len(nums1)): for j in range(i + 1, len(nums1)): res += nums22pos[nums1[i] * nums1[j]] return res
执行用时:360 ms, 在所有 Python3 提交中击败了 20.69% 的用户
内存消耗:15 MB, 在所有 Python3 提交中击败了 82.76% 的用户
算法题来源:力扣(LeetCode)