Description#
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] where 0 <= i < nums1.length and 0 <= j < k < nums2.length. - Type 2: Triplet (i, j, k) if
nums2[i]2 == nums1[j] * nums1[k] where 0 <= i < nums2.length and 0 <= 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]. (42 = 2 * 8).
Example 2:
Input: nums1 = [1,1], nums2 = [1,1,1]
Output: 9
Explanation: All Triplets are valid, because 12 = 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].
Constraints:
1 <= nums1.length, nums2.length <= 10001 <= nums1[i], nums2[i] <= 105
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
cnt1 = Counter(nums1)
cnt2 = Counter(nums2)
ans = 0
for a, x in cnt1.items():
for b, y in cnt2.items():
if a * a % b == 0:
c = a * a // b
if b == c:
ans += x * y * (y - 1)
else:
ans += x * y * cnt2[c]
if b * b % a == 0:
c = b * b // a
if a == c:
ans += x * (x - 1) * y
else:
ans += x * y * cnt1[c]
return ans >> 1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public int numTriplets(int[] nums1, int[] nums2) {
Map<Integer, Integer> cnt1 = new HashMap<>();
Map<Integer, Integer> cnt2 = new HashMap<>();
for (int v : nums1) {
cnt1.put(v, cnt1.getOrDefault(v, 0) + 1);
}
for (int v : nums2) {
cnt2.put(v, cnt2.getOrDefault(v, 0) + 1);
}
long ans = 0;
for (var e1 : cnt1.entrySet()) {
long a = e1.getKey(), x = e1.getValue();
for (var e2 : cnt2.entrySet()) {
long b = e2.getKey(), y = e2.getValue();
if ((a * a) % b == 0) {
long c = a * a / b;
if (b == c) {
ans += x * y * (y - 1);
} else {
ans += x * y * cnt2.getOrDefault((int) c, 0);
}
}
if ((b * b) % a == 0) {
long c = b * b / a;
if (a == c) {
ans += x * (x - 1) * y;
} else {
ans += x * y * cnt1.getOrDefault((int) c, 0);
}
}
}
}
return (int) (ans >> 1);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| func numTriplets(nums1 []int, nums2 []int) (ans int) {
cnt1 := map[int]int{}
cnt2 := map[int]int{}
for _, v := range nums1 {
cnt1[v]++
}
for _, v := range nums2 {
cnt2[v]++
}
for a, x := range cnt1 {
for b, y := range cnt2 {
if a*a%b == 0 {
c := a * a / b
if b == c {
ans += x * y * (y - 1)
} else {
ans += x * y * cnt2[c]
}
}
if b*b%a == 0 {
c := b * b / a
if a == c {
ans += x * (x - 1) * y
} else {
ans += x * y * cnt1[c]
}
}
}
}
ans /= 2
return
}
|
