Apakah teknik dua-penunjuk?

Question

Accepted Answer

Teknik **dua-penunjuk** menggunakan dua indeks yang bergerak melalui urutan untuk menyelesaikan masalah dalam satu lintasan — mengubah banyak solusi brute-force O(n²) menjadi **O(n)**.

## Idenya

Pertahankan dua penunjuk (sering di ujung, atau satu lambat dan satu cepat) dan gerakkan berdasarkan kondisi, mengurangi pekerjaan tanpa pemindaian ulang.

## Contoh: menemukan sepasang yang berjumlah ke target dalam array yang diurutkan

```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
```

## Kerumitan

- **Waktu:** O(n). **Ruang:** O(1).

## Kapan menggunakan / jebakan

Bagus untuk **array yang diurutkan**, pemeriksaan palindrom, pembalikan, dan menghapus duplikat di tempat. Array biasanya harus diurutkan untuk varian penunjuk yang konvergen. Berhati-hati dengan batas penunjuk dan kondisi loop (`lo < hi`).

## Mengapa ini penting

Dua penunjuk adalah salah satu pola wawancara dengan leverage tertinggi: ini menggabungkan loop bersarang menjadi pemindaian linier yang bersih.

Ini mengajarkan Anda untuk memanfaatkan struktur (seperti keselarasutamaan) daripada brute force.

Ide yang sama mendorong penggabungan, partisi, dan langkah penggabungan merge sort.