Chương trình tìm tổng cặp nhỏ nhất lớn hơn mục tiêu trong Python

Mô tả bài toán

Cho danh sách nums và giá trị target. Tìm tổng nhỏ nhất của một cặp số trong danh sách mà lớn hơn target.

Ví dụ: nums = [2, 4, 6, 10, 14], target = 10 → đầu ra 12 (cặp 2 và 10).

Giải thuật (Hai con trỏ sau khi sắp xếp)

1. Sắp xếp nums.
2. Khởi tạo answer = 10**10, i = 0, j = n-1.
3. Khi i < j:
   • Nếu nums[i] + nums[j] > target: cập nhật answer, giảm j.
   • Ngược lại: tăng i.
4. Trả về answer.

Ví dụ mã Python

class Solution:
    def solve(self, nums, target):
        nums.sort()
        n = len(nums)
        answer = 10 ** 10
        i, j = 0, n - 1
        while i < j:
            if nums[i] + nums[j] > target:
                answer = min(answer, nums[i] + nums[j])
                j -= 1
            else:
                i += 1
        return answer

ob = Solution()
nums = [2, 4, 6, 10, 14]
target = 10
print(ob.solve(nums, target))

Đầu vào

[2, 4, 6, 10, 14], 10

Đầu ra

12