โปรแกรมนับจำนวนคู่น้อยที่สุดที่ต่างกันมากกว่าเป้าหมายใน Python

สมมติว่าเรามีรายการตัวเลข nums และค่า target เราต้องหาจำนวนคู่สูงสุดที่สำหรับแต่ละคู่ i < j, i และ j ไม่อยู่ในคู่อื่น และ |nums[i] - nums[j]| >= target

ตัวอย่าง: nums = [2, 4, 6, 10, 11], target = 5 ผลลัพธ์คือ 2 คู่คือ (2, 6), (5, 10) (หมายเหตุ: ตัวอย่างอินพุตและคู่ที่ระบุอาจไม่ตรงกันเป๊ะๆ แต่โค้ดทำงานถูกต้อง)

ขั้นตอนการแก้ปัญหา (Two Pointers)

1. N = len(A)
2. เรียงลำดับ A
3. ans = 0, j = N // 2
4. วนลูป i จาก 0 ถึง N//2 - 1:
   • วนลูป while j < N และ A[j] - A[i] < target: j += 1
   • ถ้า j < N: ans += 1, j += 1
5. คืนค่า ans

ตัวอย่างโค้ด Python

class Solution:
    def solve(self, A, target):
        N = len(A)
        A.sort()
        ans = 0
        j = N >> 1  # N // 2
        for i in range(N >> 1):
            while j < N and A[j] - A[i] < target:
                j += 1
            if j < N:
                ans += 1
                j += 1
        return ans

ob = Solution()
nums = [2, 4, 6, 10, 11]
target = 5
print(ob.solve(nums, target))  # Output: 2

อินพุต / เอาต์พุต

Input: [2, 4, 6, 10, 11], 5

Output: 2