Given two arrays of integers nums1
and nums2
, return the number of triplets formed (type 1 and type 2) under the following rules:
- Type 1: Triplet (i, j, k) if
nums1[i]2 == nums2[j] * nums2[k]
where0 <= i < nums1.length
and0 <= j < k < nums2.length
. - Type 2: Triplet (i, j, k) if
nums2[i]2 == nums1[j] * nums1[k]
where0 <= i < nums2.length
and0 <= j < k < nums1.length
.
Example 1:
Input: nums1 = [7,4], nums2 = [5,2,8,9] Output: 1 Explanation: Type 1: (1,1,2), nums1[1]^2 = nums2[1] * nums2[2]. (4^2 = 2 * 8).
Example 2:
Input: nums1 = [1,1], nums2 = [1,1,1] Output: 9 Explanation: All Triplets are valid, because 1^2 = 1 * 1. Type 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]. Type 2: (0,0,1), (1,0,1), (2,0,1). nums2[i]^2 = nums1[j] * nums1[k].
Example 3:
Input: nums1 = [7,7,8,3], nums2 = [1,2,9,7] Output: 2 Explanation: There are 2 valid triplets. Type 1: (3,0,2). nums1[3]^2 = nums2[0] * nums2[2]. Type 2: (3,0,1). nums2[3]^2 = nums1[0] * nums1[1].
Example 4:
Input: nums1 = [4,7,9,11,23], nums2 = [3,5,1024,12,18] Output: 0 Explanation: There are no valid triplets.
Constraints:
1 <= nums1.length, nums2.length <= 1000
1 <= nums1[i], nums2[i] <= 10^5
Solution: Hashtable
For each number y in the second array, count its frequency.
For each number x in the first, if x * x % y == 0, let r = x * x / y
if r == y: ans += f[y] * f[y-1]
else ans += f[y] * f[r]
Final ans /= 2
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua class Solution { public: int numTriplets(vector<int>& nums1, vector<int>& nums2) { return solve(nums1, nums2) + solve(nums2, nums1); } private: int solve(vector<int>& nums1, vector<int>& nums2) { int ans = 0; unordered_map<int, int> f; for (int y : nums2) ++f[y]; for (long x : nums1) for (const auto& [y, c] : f) { long r = x * x / y; if (x * x % y || !f.count(r)) continue; if (r == y) ans += c * (c - 1); else ans += c * f[r]; } return ans / 2; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment