Chương trình tìm số cặp K-sum tối đa trong Python

Cho mảng nums và giá trị k. Một phép toán: chọn 2 phần tử tổng bằng k và xóa chúng. Tìm số phép toán tối đa.

Ví dụ: nums = [8,3,6,1,5], k = 9, đầu ra = 2 (xóa [3,6] và [8,1]).

Giải pháp

Dùng Counter đếm tần suất, ghép cặp (num, k-num):

• counter := Counter(nums)
• res := 0
• Với mỗi num trong counter:
  • Nếu counter[k-num] > 0:
    • Nếu num != k-num: res += min(counter[num], counter[k-num]); counter[k-num]=0; counter[num]=0
    • Ngược lại: res += counter[num] // 2
• Trả về res

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

from collections import Counter

def solve(nums, k):
    counter = Counter(nums)
    res = 0
    for num in counter:
        if counter.get(k-num, 0):
            if num != k - num:
                res += min(counter[num], counter[k-num])
                counter[k-num] = 0
                counter[num] = 0
            else:
                res += int(counter[num] / 2)
    return res

nums = [8,3,6,1,5]
k = 9
print(solve(nums, k))

Đầu vào

[8,3,6,1,5], 9

Đầu ra

2