Chương trình kiểm tra tổng hai số bằng k từ mảng đã sắp xếp Python

Cho mảng nums đã sắp xếp tăng dần và số k. Kiểm tra có tồn tại hai phần tử tổng bằng k không (số có thể âm hoặc 0). Yêu cầu không gian O(1).

Ví dụ: nums=[-8,-3,2,7,9], k=4 → True (7 + (-3) = 4).

Giải thuật (Hai con trỏ - Two Pointers)

1. i = 0 (đầu), j = len(nums)-1 (cuối)
2. Khi i < j:
   • cur_sum = nums[i] + nums[j]
   • Nếu cur_sum == k → True
   • Nếu cur_sum < k → i++ (cần tổng lớn hơn)
   • Nếu cur_sum > k → j-- (cần tổng nhỏ hơn)
3. Hết vòng lặp → False

Ví dụ triển khai

def solve(nums, k):
    i = 0
    j = len(nums) - 1
    while i < j:
        cur_sum = nums[i] + nums[j]
        if cur_sum == k:
            return True
        elif cur_sum < k:
            i += 1
        else:
            j -= 1
    return False

print(solve([-8, -3, 2, 7, 9], 4))

Đầu vào

[-8, -3, 2, 7, 9], 4

Đầu ra

True