Kiểm tra xem mảng đã sắp xếp có thể chia thành các cặp có tổng bằng k hay không trong Python

Giả sử chúng ta có mảng đã sắp xếp và một số k, cần kiểm tra xem mảng có thể chia thành các cặp sao cho tổng mỗi cặp bằng k hay không.

Ví dụ, arr = [1, 2, 3, 4, 5, 6], k = 7, đầu ra True vì các cặp (1,6), (2,5), (3,4) đều tổng bằng 7.

Các bước giải quyết:

• n := kích thước mảng.
• Nếu n là lẻ, trả về False.
• low := 0, high := n - 1.
• Trong khi low < high:
  • Nếu arr[low] + arr[high] != k, trả về False.
  • low += 1, high -= 1.
• Trả về True.

Xem ví dụ dưới đây để hiểu rõ hơn:

Ví dụ

def solve(arr, k):
    n = len(arr)
    if n % 2 == 1:
        return False
    low = 0
    high = n - 1
    while low < high:
        if arr[low] + arr[high] != k:
            return False
        low += 1
        high -= 1
    return True

arr = [1, 2, 3, 4, 5, 6]
k = 7
print(solve(arr, k))

Đầu vào

[1, 2, 3, 4, 5, 6], 7

Đầu ra

True