LeetCode Two Sum: ห้าแนวคิดจากช้าสุดถึงแผนที่หนึ่งรอบ

โจทย์ถามว่า ในอาเรย์ตัวเลข มีสองช่องไหนที่บวกกันได้เท่า target ให้คืนตำแหน่งทั้งสอง ข้อนี้เป็นข้อแรกที่หลายคนเจอในสัมภาษณ์

สมมติอินพุต [2, 7, 11, 15] และ target = 9 คำตอบคือตำแหน่งของ 2 กับ 7

แนวทางที่ 1: ลองทุกคู่ (Brute force)

วน i แล้ววน j > i ถ้า nums[i] + nums[j] == target ก็ตอบ

• เวลาประมาณ O(n²) พื้นที่ O(1)
• ชัดมาก เหมาะมือใหม่พิสูจน์ความเข้าใจโจทย์
• ไวท์บอร์ดใช้เปิดบทสนทนาได้ แต่ควรบอกเองว่าช้าเมื่อ n ใหญ่

แนวทางที่ 2: เรียงแล้วใช้สองตัวชี้

ถ้าโจทย์ยอมให้สนใจค่ามากกว่าตำแหน่งเดิม หรือเราสร้างคู่ (ค่า, ตำแหน่ง) แล้วเรียง ตามด้วยสองตัวชี้จากหัวท้าย

• เวลา O(n log n) จากเรียง พื้นที่ O(n) ถ้านับอาร์เรย์คู่
• ใน Two Sum มาตรฐานที่ต้องคืน index เดิม วิธีนี้พลาดง่ายถ้าลืมเก็บ index

แนวทางที่ 3: Hash map สองรอบ

รอบแรกเก็บค่าเป็นคีย์และตำแหน่งเป็นค่า รอบสองหา target - nums[i] ในแมป โดยไม่ใช้ตำแหน่งตัวเอง

• เวลา O(n) พื้นที่ O(n)
• อธิบายง่าย แต่เดินสองรอบ

แนวทางที่ 4: Hash map หนึ่งรอบ (แนะนำหลัก)

เดินทีละตัว คำนวณ need = target - nums[i] ถ้า need อยู่ในแมปแล้ว ให้ตอบ ถ้ายังไม่มี ใส่ค่าปัจจุบันลงแมป

นี่เป็นตัวอย่างโค้ดแบบ fragment / pseudocode สำหรับอธิบายแนวคิด:

def two_sum(nums, target):
    seen = {}
    for i, value in enumerate(nums):
        need = target - value
        if need in seen:
            return [seen[need], i]
        seen[value] = i

• เวลา O(n) พื้นที่ O(n)
• ชัดและเป็นคำตอบที่สัมภาษณ์ส่วนใหญ่คาดหวัง

แนวทางที่ 5: เมื่อข้อมูลพิเศษ

ถ้าอาร์เรย์เรียงอยู่แล้วและโจทย์ยอมคืนค่าแทน index หรือมีขอบเขตค่าแคบ อาจใช้สองตัวชี้หรือตารางนับ แต่ใน Two Sum คลาสสิกบน LeetCode แผนที่หนึ่งรอบยังเป็นตัวหลัก

แผนภาพด้านล่างเป็น fragment / pseudocode ของลำดับคิด:

flowchart LR
  A[อ่านค่าปัจจุบัน] --> B{need อยู่ในแมป?}
  B -->|ใช่| C[คืนสองตำแหน่ง]
  B -->|ไม่| D[เก็บค่าปัจจุบันลงแมป]
  D --> A

เลือกใช้เมื่อไหร่

สถานการณ์	แนะนำ
มือใหม่เพิ่งอ่านโจทย์	Brute force แล้วค่อยย่น
ไวท์บอร์ดสัมภาษณ์	Hash map หนึ่งรอบ พร้อมพูด tradeoff พื้นที่
โปรดักชัน hot path	Hash map หนึ่งรอบ หรือโครงสร้างที่เหมาะข้อมูลจริงหลังวัดแล้ว

Recap

• พูดโจทย์และตัวอย่างก่อนลงโค้ด
• เริ่มจาก O(n²) ได้ แต่จบที่ O(n) ด้วยแมป
• ระวังคืน index เดิม ไม่ใช่ค่า
• ทบทวนเคสตัวเลขซ้ำและไม่มีคำตอบตามสัญญาโจทย์ครับ