İki işaretçi tekniği nedir?

Question

Accepted Answer

**İki işaretçi** tekniği, bir dizi boyunca hareket eden iki indeks kullanarak sorunları tek bir geçişte çözer — birçok O(n²) brute-force çözümünü **O(n)** haline dönüştürür.

## Fikir

İki işaretçi tutun (genellikle uçlarda veya biri yavaş biri hızlı) ve bir koşula göre bunları hareket ettirerek, yeniden taramadan işi azaltın.

## Örnek: sıralanmış bir dizide hedef değere toplamı verilen bir çifti bulma

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

## Karmaşıklık

- **Zaman:** O(n). **Alan:** O(1).

## Ne zaman kullanılır / tuzaklar

**Sıralanmış diziler**, palindrom kontrolleri, ters çevirme ve yinelenenleri yerinde kaldırma için harikadır. Dizi sıklıkla yakınsayan işaretçi değişkeni için sıralanmış olmalıdır. İşaretçi sınırları ve döngü koşulu (`lo < hi`) hakkında dikkatli olun.

## Neden önemli

İki işaretçi, en yüksek etkiye sahip mülakat desenlerinden biridir: iç içe döngüleri temiz bir doğrusal taramaya çökertirir.

Sizi brute force yerine yapı (örneğin sıralanmış olma durumu) kullanmayı öğretir.

Aynı fikir birleştirme, bölümleme ve merge sort'un birleştirme adımını güçlendirir.