เทคนิคสองตัวชี้คืออะไร?

Question

Accepted Answer

เทคนิค **สองตัวชี้** ใช้สองดัชนีที่เคลื่อนไหวผ่านลำดับเพื่อแก้ไขปัญหาในการผ่านครั้งเดียว — เปลี่ยนวิธีแก้ปัญหา brute-force O(n²) จำนวนมากให้เป็น **O(n)**

## ความคิด

เก็บตัวชี้สองตัว (มักอยู่ที่ปลาย หรือตัวหนึ่งช้าและตัวหนึ่งเร็ว) และเคลื่อนไหวตามเงื่อนไข ลดปริมาณงานโดยไม่ต้องสแกนซ้ำ

## ตัวอย่าง: ค้นหาคู่ที่รวมเป็นค่าเป้าหมายในอาร์เรย์ที่เรียงลำดับ

```python
def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)       # found the pair
        elif s < target:
            lo += 1               # need a bigger sum
        else:
            hi -= 1               # need a smaller sum
    return None

two_sum_sorted([1, 3, 4, 6, 9], 10)   # -> (1, 3) for 4 + 6
```

## ความซับซ้อน

- **เวลา:** O(n) **พื้นที่:** O(1)

## เมื่อใดควรใช้ / ข้อผิดพลาด

เหมาะสำหรับ **อาร์เรย์ที่เรียงลำดับ** การตรวจสอบพาลินโดรม การย้อนกลับ และการลบที่ซ้ำกันในที่ อาร์เรย์มักต้องเรียงลำดับสำหรับตัวแปรตัวชี้บรรจบ ระวังเกี่ยวกับขอบเขตตัวชี้และเงื่อนไขลูป (`lo < hi`)

## เหตุใดจึงมีความสำคัญ

สองตัวชี้เป็นหนึ่งในรูปแบบการสัมภาษณ์ที่มีประสิทธิภาพสูงสุด: มันทำให้ลูปที่ซ้อนกันยุบลงเป็นสแกนเชิงเส้นที่สะอาด

มันสอนให้คุณใช้ประโยชน์จากโครงสร้าง (เช่น การเรียงลำดับ) แทนการใช้กำลังดุร้าย

ความคิดเดียวกันนี้ขับเคลื่อนการผสาน การแบ่งพาร์ติชั่น และขั้นตอนการผสานของ merge sort