LeetCode 15 3Sum: sort แล้วบีบสองฝั่งเพื่อคุมชุดซ้ำ

โจทย์ 3Sum ขอชุดสามจำนวนที่รวมเป็นศูนย์โดยห้ามผลลัพธ์ซ้ำครับ ความยากจึงมีสองชั้น: หาให้ครบ และกำจัด duplicate โดยไม่เสียเวลาเกินจำเป็น

วิธีที่ 1: sort + two pointers

เรียง array แล้วตรึงค่าตัวแรก จากนั้นเลื่อน left/right ตามผลรวม หากรวมต่ำไปขยับซ้าย สูงไปขยับขวา และข้ามค่าซ้ำหลังพบคำตอบ

• เวลา O(n²) หลัง sort O(n log n)
• memory เพิ่ม O(1) หาก sort in place หรือ O(n) หาก copy เพื่อรักษา input
• duplicate handling ชัดและเป็น best default

วิธีที่ 2: hash set ต่อ pivot

ตรึงค่าแรกแล้วเดินค่าที่สอง เก็บค่าที่เห็นเพื่อหา complement วิธีนี้ยัง O(n²) และใช้ O(n) memory โดยไม่ต้องเรียง แต่ต้อง canonicalize tuple เพื่อ deduplicate ผลลัพธ์

วิธีที่ 3: brute force เป็น oracle

ลองทุกสาม index ใช้เวลา O(n³) แต่สั้นและเชื่อถือได้สำหรับ array เล็ก จึงมีประโยชน์มากใน property test เปรียบเทียบ implementation เร็ว

import unittest


def three_sum_two_pointers(nums):
    values = sorted(nums)
    result = []
    for index in range(len(values) - 2):
        if index and values[index] == values[index - 1]:
            continue
        if values[index] > 0:
            break
        left, right = index + 1, len(values) - 1
        while left < right:
            total = values[index] + values[left] + values[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                result.append((values[index], values[left], values[right]))
                left += 1
                right -= 1
                while left < right and values[left] == values[left - 1]:
                    left += 1
                while left < right and values[right] == values[right + 1]:
                    right -= 1
    return set(result)


def three_sum_hash(nums):
    result = set()
    for index, first in enumerate(nums):
        seen = set()
        for second in nums[index + 1:]:
            third = -first - second
            if third in seen:
                result.add(tuple(sorted((first, second, third))))
            seen.add(second)
    return result


def three_sum_bruteforce(nums):
    result = set()
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            for k in range(j + 1, len(nums)):
                if nums[i] + nums[j] + nums[k] == 0:
                    result.add(tuple(sorted((nums[i], nums[j], nums[k]))))
    return result


class ThreeSumTests(unittest.TestCase):
    def check(self, nums, expected):
        self.assertEqual(three_sum_two_pointers(nums), expected)
        self.assertEqual(three_sum_hash(nums), expected)
        self.assertEqual(three_sum_bruteforce(nums), expected)

    def test_examples_and_duplicates(self):
        self.check([-1, 0, 1, 2, -1, -4], {(-1, -1, 2), (-1, 0, 1)})
        self.check([0, 0, 0, 0], {(0, 0, 0)})
        self.check([1, 2, -2, -1], set())


if __name__ == "__main__":
    unittest.main()

Decision table

สถานการณ์	Sort + two pointers	Hash per pivot	Brute force
input ใหญ่	ดีที่สุดทั่วไป	ใช้ได้แต่ memory เพิ่ม	ไม่เหมาะ
memory จำกัด	ดีถ้ายอม sort in place	O(n)	O(1) แต่ช้า
readability	duplicate rule ชัด	complement คุ้นเคย	ง่ายสุด
input เรียงอยู่แล้ว	ได้เปรียบมาก	ไม่ได้ใช้ลำดับ	ไม่ได้ใช้ลำดับ
ห้ามแก้ input	copy ก่อน sort	ผ่าน	ผ่าน
oracle สำหรับ test	ดี	ดี	ดีที่สุดเมื่อ n เล็ก

Best default: sort copy แล้วใช้ two pointers เพราะเวลา O(n²) และควบคุม duplicate โดยไม่พึ่ง result set ขนาดใหญ่

Edge cases

• จำนวนศูนย์มากกว่าสามตัวต้องคืนชุดเดียว
• ค่าซ้ำทั้ง pivot และ pointer ต้องข้ามให้ครบ
• น้อยกว่าสามสมาชิกคืนว่าง
• ภาษา fixed-width ต้องใช้ชนิดที่รวมสามค่าไม่ overflow

Recap

• sort ช่วยให้ผลรวมบอกทิศทาง pointer
• ข้าม duplicate ทั้ง pivot และหลังพบคำตอบ
• copy ก่อน sort หาก input order เป็นของผู้เรียก
• ใช้ brute force เป็น oracle กับเคสเล็ก