โปรแกรมหาจำนวนคู่ K-sum สูงสุดใน Python

สมมติว่าเรามีอาร์เรย์ชื่อ nums และอีกค่าหนึ่ง k ในหนึ่งการดำเนินการ เราสามารถเลือกสององค์ประกอบจาก nums ที่ผลรวมเท่ากับ k และลบพวกมันออกจากอาร์เรย์ เราต้องหาจำนวนการดำเนินการสูงสุดที่เราสามารถทำได้บนอาร์เรย์

เช่น ถ้าอินพุตคือ nums = [8,3,6,1,5] k = 9 ผลลัพธ์จะเป็น 2 เพราะเราสามารถลบ [3,6] ที่ผลรวม 9 แล้วลบ [8,1] ที่ผลรวมก็ 9

วิธีแก้ปัญหา

• counter := แมปเก็บความถี่ของแต่ละ item ใน nums
• res := 0
• สำหรับแต่ละ num ใน counter:
  • ถ้า counter[k-num] ไม่เป็นศูนย์:
    • ถ้า num ไม่เท่ากับ k - num:
      • res := res + min(counter[num], counter[k-num])
      • counter[k-num] := 0
      • counter[num] := 0
    • มิฉะนั้น:
      • res := res + ผลหารของ (counter[num] / 2)
• return res

ตัวอย่าง

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))

อินพุต

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

เอาต์พุต

2