โปรแกรมหาจำนวนคู่ที่ผลรวมกำลังสองอยู่ในช่วงที่กำหนดใน Python

สมมติว่าเรามีรายการตัวเลขสองรายการ nums1 และ nums2 พร้อมกับตัวเลข lower และ upper เราต้องหาจำนวนคู่ (i, j) ที่ทำให้ lower <= nums1[i]^2 + nums2[j]^2 <= upper

เช่น ถ้าอินพุตคือ nums1 = [5, 3, 2], nums2 = [8, 12, 6], lower = 10, upper = 50 ผลลัพธ์จะเป็น 2 เพราะคู่คือ (1, 2) และ (2, 2):

• 10 <= 3^2 + 6^2 <= 50 = 10 <= 45 <= 50
• 10 <= 2^2 + 6^2 <= 50 = 10 <= 40 <= 50

ขั้นตอนการแก้ปัญหา

1. แทนที่แต่ละสมาชิกด้วยกำลังสองใน nums1 และ nums2
2. n := ขนาดของ nums1, m := ขนาดของ nums2
3. ถ้า n > m สลับ nums1 กับ nums2 และ n กับ m
4. nums2 := เรียงลำดับ nums2
5. res := 0
6. สำหรับแต่ละ e1 ใน nums1:
   • st := ตำแหน่งซ้ายสุดที่แทรก (lower - e1) ลง nums2 ให้เรียงลำดับ
   • en := ตำแหน่งขวาสุดที่แทรก (upper - e1) ลง nums2 ให้เรียงลำดับ
   • count := en - st
   • res := res + count
7. คืนค่า res

ตัวอย่างการใช้งาน

from bisect import bisect_left, bisect_right

def solve(nums1, nums2, lower, upper):
    nums1 = [i * i for i in nums1]
    nums2 = [i * i for i in nums2]
    n, m = len(nums1), len(nums2)
    if n > m:
        nums1, nums2 = nums2, nums1
        n, m = m, n
    nums2 = sorted(nums2)
    res = 0
    for e1 in nums1:
        st = bisect_left(nums2, lower - e1)
        en = bisect_right(nums2, upper - e1)
        count = en - st
        res += count
    return res

nums1 = [5, 3, 2]
nums2 = [8, 12, 6]
lower = 10
upper = 50
print(solve(nums1, nums2, lower, upper))

อินพุต

[5, 3, 2], [8, 12, 6], 10, 50

เอาต์พุต

2