Time & Space

Two Sum คืออะไร

**Two Sum** เป็นโจทย์คลาสสิกที่มักถูกใช้สัมภาษณ์งานสายโปรแกรมเมอร์ โจทย์นี้จะให้เราฝึกคิด **Trade-off** — การแลกระหว่างเวลา (Time) และเนื้อที่ (Space) อย่างเป็นรูปธรรม **โจทย์:** ให้อาเรย์ของตัวเลข `nums` และตัวเลขเป้าหมาย `target` ให้หา **สองตัวเลขในอาเรย์ที่รวมกันเท่ากับ target** และคืนค่า **index** ของสองตำแหน่งนั้น **ข้อกำหนด:** - แต่ละ input จะมีคำตอบเพียงหนึ่งเดียวเสมอ (exactly one solution) - ห้ามใช้ตัวเลขเดิมซ้ำ (you may not use the same element twice) - index ที่คืนค่าจะเรียงลำดับยังไงก็ได้

• **ตัวอย่างที่ 1:** `nums = [2, 7, 11, 15]`, `target = 9` `2 + 7 = 9` → คืนค่า `[0, 1]`
• **ตัวอย่างที่ 2:** `nums = [3, 2, 4]`, `target = 6` `2 + 4 = 6` → คืนค่า `[1, 2]`
• **ตัวอย่างที่ 3:** `nums = [3, 3]`, `target = 6` `3 + 3 = 6` → คืนค่า `[0, 1]` (คนละตำแหน่ง แต่ค่าเท่ากันได้)

แนวทางที่ 1: Brute Force — O(n²) Time, O(1) Space

วิธีที่ตรงไปตรงมาที่สุดคือ **ไล่เช็คทุกคู่** — ใช้ nested loop จับคู่ตัวเลขทีละคู่จนเจอคู่ที่รวมกันได้ target **Time Complexity:** O(n²) — เพราะต้องเช็คทุกคู่ใน worst case (n × (n-1) / 2 ≈ n²) **Space Complexity:** O(1) — ใช้แค่ตัวแปร loop ไม่สร้างข้อมูลใหม่

function twoSumBruteForce(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return [-1, -1]; // ไม่เจอคำตอบ (ไม่ควรเกิดตามข้อกำหนด)
}

// ทดสอบ
console.log(twoSumBruteForce([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSumBruteForce([3, 2, 4], 6));      // [1, 2]
console.log(twoSumBruteForce([3, 3], 6));         // [0, 1]

วิธีนี้ทำงานได้กับทุก input แต่จะช้ามากเมื่อ n ใหญ่ขึ้น เช่นถ้า n = 10,000 จะต้องเช็คประมาณ 50 ล้านครั้ง

แนวทางที่ 2: Hash Map — O(n) Time, O(n) Space

เราใช้ **Object (Hash Map)** เพื่อให้ค้นหาว่า complement (ค่าที่ต้องหาเพิ่ม) เคยเจอมาก่อนหรือยังใน O(1) Time **แนวคิด:** - วน loop ไปทีละตัวเลข - หา **complement** = `target - nums[i]` (เลขที่ต้องเอามาบวกให้ได้ target) - ถ้า complement เคยเห็นแล้วใน Object → เจอคำตอบ - ถ้ายังไม่เคยเห็น → เก็บตัวเลขปัจจุบันใส่ Object (`{ค่า: index}`)

function twoSum(nums, target) {
  const seen = {}; // Object เก็บ {ค่าตัวเลข: index}

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen[complement] !== undefined) {
      return [seen[complement], i];
    }
    seen[nums[i]] = i;
  }
  return [-1, -1];
}

// ทดสอบ
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSum([3, 2, 4], 6));      // [1, 2]
console.log(twoSum([3, 3], 6));         // [0, 1]

**Time Complexity:** O(n) — วน loop ครั้งเดียว ค้นหาใน Object ใช้ O(1) **Space Complexity:** O(n) — worst case เก็บทุกตัวเลขใน Object **Trade-off:** เรา **แลกพื้นที่ (Space) เพื่อซื้อเวลา (Time)** — ใช้หน่วยความจำมากขึ้นเพื่อให้เร็วขึ้น

เปรียบเทียบ Time vs Space

การเลือกใช้วิธีไหนขึ้นอยู่กับ **ขนาด input (n)** และ **ข้อจำกัดด้านหน่วยความจำ** - n ≤ 100 → brute force ก็พอ ต่างกันแค่ไม่กี่ millisecond - n ≥ 10,000 → ต้องใช้ hash map ไม่งั้นรอนานเกิน - หน่วยความจำจำกัดมาก → brute force ปลอดภัยกว่า

กฎสำคัญ: Time-Space Trade-off

สรุป: Two Sum — Time-Space Trade-off

**ข้อคิดสำคัญ:** เราสามารถ **outperform เวลาได้ด้วยการเพิ่มพื้นที่** เมื่อเรายอมใช้หน่วยความจำมากขึ้น เราสามารถทำเวลาได้ดีขึ้น คีย์สำคัญคือการหา **โครงสร้างข้อมูลที่เหมาะสม** สำหรับ lookup (ในกรณีนี้คือ Object/Hash Map ที่ใช้ O(1))

ทบทวนความเข้าใจ: Two Sum