Chương trình đếm số cặp phân biệt tối đa có hiệu lớn hơn target bằng Python

Cho danh sách nums và giá trị target. Tìm số cặp tối đa với điều kiện i < j, mỗi chỉ số chỉ thuộc một cặp, và |nums[i] - nums[j]| >= target.

Ví dụ: nums = [2, 4, 6, 10, 11], target = 5 → 2 (cặp (2, 6) và (4, 10)).

Quy trình giải quyết (Two Pointers sau khi sắp xếp)

1. Sắp xếp mảng A.
2. Khởi tạo ans = 0, j = N // 2.
3. Với i từ 0 đến N//2 - 1:
   • Tăng j cho đến khi A[j] - A[i] >= target.
   • Nếu j < N, tăng ans và j++.
4. Trả về ans.

Ví dụ mã nguồn

class Solution:
    def solve(self, A, target):
        N = len(A)
        A.sort()
        ans = 0
        j = N >> 1
        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

Đầu vào

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

Đầu ra

2