โจทย์
ให้อาร์เรย์สองอาร์เรย์ nums1 และ nums2 เราต้องหาจำนวนทริปเล็ต (triplet) ที่สร้างขึ้นตามกฎสองประเภทดังนี้:
- ประเภท 1: ทริปเล็ต (i, j, k) โดยที่
nums1[i]² = nums2[j] * nums2[k]โดยที่0 ≤ i < ขนาดของ nums1และ0 ≤ j < k < ขนาดของ nums2 - ประเภท 2: ทริปเล็ต (i, j, k) โดยที่
nums2[i]² = nums1[j] * nums1[k]โดยที่0 ≤ i < ขนาดของ nums2และ0 ≤ j < k < ขนาดของ nums1
ตัวอย่าง: หาก nums1 = [7,4] และ nums2 = [5,2,8,9] ผลลัพธ์คือ 1 เพราะมีทริปเล็ตประเภท 1 คือ (1,1,2) ที่ nums1[1]² = nums2[1] * nums2[2] (16 = 2×8)
วิธีแก้ปัญหา
- สร้าง
cnt1และcnt2เป็นแผนที่ (map) ที่เก็บจำนวนครั้งที่แต่ละค่าปรากฏในnums1และnums2ตามลำดับ - กำหนดฟังก์ชัน
triplets(arr1, arr2)ที่คืนค่าจำนวนทริปเล็ตที่ตรงตามเงื่อนไขarr1[i]² = arr2[j] * arr2[k] - ในฟังก์ชัน
triplets:- วนลูปผ่านค่า
tและความถี่vในarr1 - คำนวณ
k = arr2.get(t, 0)(จำนวนครั้งที่tปรากฏในarr2) - คำนวณจำนวนคู่ (j,k) ที่
j < kและทั้งคู่มีค่าเท่ากับtคือk*(k-1)/2 - คำนวณ
sq = t * t - วนลูปผ่านค่า
mในarr2ที่m < tและsq % m == 0แล้วบวกarr2[m] * arr2[sq//m] - รวมผลลัพธ์คูณด้วย
v
- วนลูปผ่านค่า
- ผลลัพธ์สุดท้ายคือ
triplets(cnt1, cnt2) + triplets(cnt2, cnt1)
ตัวอย่างโค้ด
from collections import Counter
def solve(nums1, nums2):
cnt1 = Counter(nums1)
cnt2 = Counter(nums2)
def triplets(arr1, arr2):
ans = 0
for t, v in arr1.items():
k = arr2.get(t, 0)
tmp = k * (k - 1) // 2
sq = t * t
for m in arr2:
if m < t and sq % m == 0:
tmp += arr2.get(m, 0) * arr2.get(sq // m, 0)
ans += tmp * v
return ans
return triplets(cnt1, cnt2) + triplets(cnt2, cnt1)
nums1 = [7, 4]
nums2 = [5, 2, 8, 9]
print(solve(nums1, nums2)) # Output: 2
อินพุต / เอาต์พุต
Input: [7,4],[5,2,8,9]
Output: 2
