LeetCode #15 3Sum: หาสามตัวที่บวกกันได้ศูนย์โดยไม่ซ้ำชุด

เคยนั่งแบ่งบิลกับเพื่อน แล้วอยากหาสามใบเสร็จที่รวมกันพอดีศูนย์หรือเปล่า โจทย์ 3Sum คือแบบนั้นครับ ให้ array ของจำนวนเต็ม หาทุกชุดสามตัวที่บวกกันได้ 0 โดยชุดที่เลขเหมือนกันนับครั้งเดียว ไม่สนลำดับในชุด

วิธีที่ 1: ลองทุกสามตัว (brute force)

วนสามชั้นเลือก i < j < k แล้วเช็กผลรวม เก็บผลใน set ของทูเพิลที่เรียงแล้วเพื่อตัดซ้ำ เวลา O(n³) พื้นที่ O(t) ตามจำนวนคำตอบ ดีตอนเรียนนิยามโจทย์และใช้เป็น oracle ทดสอบข้อมูลเล็ก ข้อเสียคือช้าเกิน constraints จริง

วิธีที่ 2: ตรึงหนึ่งตัวแล้วหาคู่ด้วย hash

ตรึง nums[i] แล้วเดิน j > i เก็บค่าที่เคยเห็นใน set หาว่ามี need = -nums[i] - nums[j] หรือไม่ เวลาเฉลี่ย O(n²) พื้นที่ O(n) ต่อรอบ ตัดซ้ำยังต้องเรียงทูเพิลก่อนใส่ set ข้อควรระวังคือค่าซ้ำหลายตัวอาจสร้างชุดซ้ำถ้าไม่ข้ามดัชนีที่เคยใช้

วิธีที่ 3: sort + two pointers (แนะนำหลัก)

เรียง array ก่อน แล้วตรึง i จากซ้าย ใช้ left/right หาคู่ที่รวมกับ nums[i] ได้ศูนย์ ถ้าผลรวมน้อยเกินไปขยับ left ถ้ามากเกินไปขยับ right เมื่อเจอคำตอบแล้วต้องข้ามค่าซ้ำทั้งสามด้าน เวลา O(n²) พื้นที่ O(1) นอกจากผลลัพธ์ (ไม่นับพื้นที่เรียงตามภาษา)

Invariant สำคัญ: หลังเรียงแล้ว ช่องว่างระหว่าง left กับ right หดลงทุกก้าว และค่าซ้ำถูกข้ามทันทีหลังเก็บคำตอบ จึงไม่สร้างชุดซ้ำ

วิธีที่ 4: early skip กับ prune

ต่อจากวิธี 3 ถ้า nums[i] > 0 หยุดได้เลย เพราะตัวที่ตามมาก็เป็นบวก ถ้า nums[i] == nums[i-1] ข้ามเพื่อไม่เริ่มชุดซ้ำ และถ้า nums[i] + nums[i+1] + nums[i+2] > 0 ก็ prune ได้เช่นกัน ช่วยตัดเคสว่างเร็ว แต่ไม่เปลี่ยน big-O

def three_sum(nums):
    nums = sorted(nums)
    n = len(nums)
    out = []
    for i in range(n):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        if nums[i] > 0:
            break
        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                out.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return out


samples = [
    ([-1, 0, 1, 2, -1, -4], [[-1, -1, 2], [-1, 0, 1]]),
    ([0, 1, 1], []),
    ([0, 0, 0], [[0, 0, 0]]),
]
for nums, expected in samples:
    got = three_sum(nums)
    assert got == expected, (nums, got, expected)
print("ok", len(samples), "cases")

เลือกตามสถานการณ์

สถานการณ์	วิธีที่เหมาะ	เหตุผลสั้นๆ
อธิบายโจทย์ / สร้าง test oracle	brute force	ตรงนิยามที่สุด
ไม่อยากเรียง / จำค่าเร็ว	hash pair	O(n²) โดยไม่พึ่งลำดับ
สัมภาษณ์และ production ทั่วไป	sort + two pointers	O(n²)/O(1) และตัดซ้ำชัด
ข้อมูลมีศูนย์หรือเลขบวกเยอะ	two pointers + prune	ตัดรอบว่างเร็ว

เคสที่ผมเคยพลาด: เลขซ้ำหลายตัว, ทั้งอาเรย์เป็นศูนย์, มีแค่สองตัว, และค่าบวกทั้งหมดหลังเรียง อย่าลืมข้ามซ้ำหลังเจอคำตอบ ไม่ใช่แค่ตอนเริ่ม i

Recap

• เรียงก่อน แล้วตรึงหนึ่งตัวใช้ two pointers หาคู่ที่รวมได้ศูนย์
• ข้ามค่าซ้ำทั้งที่ i, left, และ right
• ถ้า nums[i] > 0 หยุดได้
• ใช้ brute force เทียบผลบน input สั้นก่อนเชื่อวิธีเร็ว
• default เลือก sort + two pointers ครับ