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

Giả sử chúng ta có một mảng gọi là nums và một giá trị khác k. Trong một thao tác, chúng ta có thể chọn hai phần tử từ các num có tổng bằng k và xóa chúng khỏi mảng. Chúng ta phải tìm số lượng phép toán tối đa mà chúng ta có thể thực hiện trên mảng.

Vì vậy, nếu đầu vào là nums =[8,3,6,1,5] k =9, thì đầu ra sẽ là 2 vì chúng ta có thể xóa [3,6] có tổng là 9, sau đó xóa [8,1 ] có tổng cũng là 9.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• bộ đếm:=tần suất lưu giữ bản đồ của mỗi mục hiện diện bằng nums
• res:=0
• đối với mỗi số trong bộ đếm, thực hiện
  • nếu bộ đếm [k-num] khác 0, thì
    • nếu num không giống k - num, thì
      • res:=res + tối thiểu của bộ đếm [num] và bộ đếm [k-num]
      • bộ đếm [k-num]:=0
      • bộ đếm [num]:=0
    • nếu không,
      • res:=res + thương số của (counter [num] / 2)
• trả lại res

Ví dụ

Hãy cùng chúng tôi xem cách 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