ข้อ 13 · LC1679 Max Number of K-Sum Pairs 🟡

ให้ array (ลิสต์) nums และเลข k ในหนึ่ง operation (การกระทำ) เราเลือกเลขสองตัวที่บวกกันได้ k แล้วนำทั้งคู่ ออกจาก array จง return จำนวน operation มากที่สุดที่ทำได้

จุดที่ต้องระวัง: เลขแต่ละตัวใช้ได้ครั้งเดียว เพราะถูกเอาออกไปแล้ว

ลองเองก่อน 10–15 นาที

def max_operations(nums: list[int], k: int) -> int:
    # เขียนโค้ดของคุณที่นี่
    pass


print(max_operations([1, 2, 3, 4], 5))      # ควรได้ 2
print(max_operations([3, 1, 3, 4, 3], 6))   # ควรได้ 1
print(max_operations([2, 2, 2, 3], 4))      # ควรได้ 1

# ทางที่ 1: two pointers
nums.sort()
left, right = 0, len(nums) - 1
ops = 0
while left < right:
    total = nums[left] + nums[right]
    if total == k:
        ops += 1
        ______        # (1) ขยับอะไรบ้าง (คำใบ้: สองบรรทัด)
    elif total < k:
        ______        # (2)
    else:
        ______        # (3)
return ops

# ทางที่ 2: นับด้วย dict ธรรมดา
need = {}                     # ค่าที่ "รอคู่" -> เหลือกี่ตัว
ops = 0
for x in nums:
    if need.get(______, 0) > 0:   # (4) มีตัวที่รอจับกับ x อยู่ไหม
        need[______] -= 1         # (5) ใช้มันไปหนึ่งตัว
        ops += 1
    else:
        need[x] = need.get(x, 0) + 1   # x เข้าคิวรอคู่
return ops

ไล่ทีละสเต็ปด้วยมือ (dry run)

แบบ two pointers บน nums = [3, 1, 3, 4, 3], k = 6 — sort ก่อนได้ [1, 3, 3, 3, 4]

ตอบ 1 ตรงกับ Example 2 — และเห็นชัดว่าเลข 3 ที่เหลือตัวเดียวจับกับใครไม่ได้

แบบนับด้วย dict บนชุดเดิม [3, 1, 3, 4, 3], k = 6 (ไม่ต้อง sort ไล่ตามลำดับที่ให้มาเลย)

ทำไมมันถูกต้อง: โจทย์นี้ไม่มีอะไรให้เลือกเลย

คำว่า "ให้ได้มากที่สุด" ในโจทย์ทำให้ดูเหมือนเป็นปัญหาที่ต้องเลือกให้ฉลาด — เลือกผิดคู่ตอนต้นแล้วอาจเสียคู่ตอนท้าย เหมือนโจทย์จับคู่ทั่วไป แต่ข้อนี้ไม่ใช่ และเข้าใจข้อนี้ได้แล้วโจทย์จะยุบทั้งข้อ

เหตุผล: เลข x จับได้กับ k − x เท่านั้น ค่าเดียว ไม่มีตัวเลือกที่สอง ดังนั้นตัวเลขทั้งหมดจึงถูกแบ่งเป็น กลุ่มที่ไม่เกี่ยวข้องกันเลย โดยแต่ละกลุ่มมีแค่สองค่าคือ x กับ k − x การตัดสินใจในกลุ่มหนึ่งไม่กระทบอีกกลุ่มแม้แต่นิดเดียว

nums = [1, 5, 2, 4, 2, 4, 4, 3]   k = 6

แบ่งเป็นกลุ่มที่ไม่เกี่ยวกันเลย:

  กลุ่ม (1, 5) : มี 1 อยู่ 1 ตัว , มี 5 อยู่ 1 ตัว  ->  จับได้ min(1, 1) = 1 คู่
  กลุ่ม (2, 4) : มี 2 อยู่ 2 ตัว , มี 4 อยู่ 3 ตัว  ->  จับได้ min(2, 3) = 2 คู่
  กลุ่ม (3, 3) : มี 3 อยู่ 1 ตัว (x = k - x)        ->  จับได้ 1 // 2 = 0 คู่

  รวม = 1 + 2 + 0 = 3 คู่   <- ไม่มีการเลือกใดที่ทำให้ได้มากกว่านี้

ดูบรรทัด "กลุ่ม (2, 4)" ให้ดี: มีเลข 2 อยู่สองตัวและเลข 4 อยู่สามตัว จับได้มากสุด 2 คู่ ไม่ว่าจะจับตัวไหนกับตัวไหน เพราะ 2 หมดก่อน เลข 4 ที่เหลืออีกตัวจับกับใครไม่ได้เลยเนื่องจากคู่ของมันคือ 2 ซึ่งหมดแล้ว จำนวนคู่ของแต่ละกลุ่มจึงเป็น min(จำนวนของ x, จำนวนของ k − x) ตายตัว ไม่ใช่ผลของการเลือกที่ดี

กรณีพิเศษคือกลุ่มที่ x = k − x (คู่ของมันคือตัวมันเอง เช่น k = 6 กับ x = 3) กลุ่มนี้ต้องใช้ของสองตัวจากกองเดียวกัน จึงได้จำนวนคู่เท่ากับ จำนวนของ x หารสองปัดลง เช่นมี 3 อยู่ห้าตัวก็ได้ 2 คู่ เหลือเศษหนึ่งตัว — ตรงกับ Example 3 ในโจทย์ที่มีเลข 2 สามตัวแล้วจับได้แค่คู่เดียว

แล้วข้อนี้ sort ได้ ทั้งที่หน้าแนวคิดบอกว่าบางข้อ sort ไม่ได้

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

เทียบกับ LC1 Two Sum ที่หน้าแนวคิดยกเป็นตัวอย่างว่า sort ไม่ได้ — ข้อนั้นต้อง return index ของตัวเลขในแถวเดิม การเรียงจึงทำลายคำตอบทิ้ง ความต่างของสองข้ออยู่ที่สิ่งที่โจทย์ขอให้ return เท่านั้น ไม่ได้อยู่ที่ตัวอัลกอริทึม

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        nums.sort()                        # (1) แบบที่ 1 ต้องการข้อมูลที่เรียงแล้ว
        left, right = 0, len(nums) - 1
        ops = 0

        while left < right:                # (2) ยังเหลือเลขให้จับอย่างน้อย 2 ตัว
            total = nums[left] + nums[right]
            if total == k:                 # (3) เจอคู่
                ops += 1
                left += 1                  # (4) เอาออกทั้งสองตัว
                right -= 1
            elif total < k:                # (5) น้อยไป ต้องการค่าซ้ายที่ใหญ่ขึ้น
                left += 1
            else:                          # (6) มากไป ต้องการค่าขวาที่เล็กลง
                right -= 1

        return ops

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        need = {}                          # ค่าที่ยัง "รอคู่" -> เหลือกี่ตัว
        ops = 0

        for x in nums:
            if need.get(k - x, 0) > 0:     # มีตัวที่รอจับกับ x อยู่ไหม
                need[k - x] -= 1           # ใช้มันไปหนึ่งตัว เท่ากับจับคู่สำเร็จ
                ops += 1
            else:
                need[x] = need.get(x, 0) + 1   # ยังไม่มีคู่ ให้ x เข้าคิวรอ

        return ops

from collections import defaultdict


def max_operations_hash_v2(nums: list[int], k: int) -> int:
    need = defaultdict(int)       # เหมือน dict ธรรมดา แต่อ่าน key ใหม่แล้วได้ 0 อัตโนมัติ
    ops = 0
    for x in nums:
        if need[k - x] > 0:
            need[k - x] -= 1
            ops += 1
        else:
            need[x] += 1
    return ops


print(max_operations_hash_v2([3, 1, 3, 4, 3], 6))

1