Kalıp #02
İki İşaretçi
TemelSıralı diziler, çift koşulları veya iki uçtan koordineli hareket.
Ne zaman kullanılır
Sıralı dizilerde çift/üçlü toplamlar için veya karşılaştırmaya göre hangi ucu hareket ettireceğini bildiğinde. Yerinde ters çevirme/bölme için de.
Tanıma ipuçları
- Dizi sıralı (veya cevabı bozmadan sıralanabilir)
- Hedef toplama sahip çift / üçlü bul
- Karşıt uçlar, ortada buluş
- Yerinde yinelenenleri sil
Yaygın tuzaklar
- Orijinal indeksler gerektiğinde sıralamak (önce indeksleri sakla)
- Eşleşmeden sonra işaretçiyi hareket ettirmeyi unutup sonsuz döngü
- 3Sum tarzı problemlerde yinelenenleri ele alma
90 saniyelik tanıma egzersizi
Hangisi en iyi uyuyor?
- Dizi sıralı (veya cevabı bozmadan sıralanabilir)
- Hedef toplama sahip çift / üçlü bul
- Karşıt uçlar, ortada buluş
Interactive
Zihinsel model
Değişmezin tam adım adım anlatımı. Duraklat, noktalara tıkla veya ← → kullan. Her adımı kendi cümlelerinle anlatmayı hedefle.
L = 0, R = n-1
Sorted array. Find a pair that sums to target 9.
Nasıl düşünülür
left başta, right sonda (veya aynı yön varyantlarında ikisi de başta). Her adımda karşılaştır ve cevabı iyileştirebilecek işaretçiyi hareket ettir. Çift toplamlar için karşıt uçlar; yerinde bölümler için aynı yön.
Yaygın varyantlar
| Varyant | Hareket | Örnek |
|---|---|---|
| Karşıt uçlar | toplam vs hedefe göre left++ / right– | Two Sum II |
| Aynı yön | yerinde yazım için slow/fast | Yinelenenleri sil |
| Kap | daha kısa yüksekliği içeri al | Container With Most Water |
Karmaşıklık temeli
Sıralamadan sonra O(n) (sıralama genelde O(n log n)). Sonuç saklamadıkça sabit ekstra alan.
Şablon
TypeScript, Python ve C#’te aynı iskelet. Değişmezi uyarla; yapıyı koru.
/** Two pointers template: sorted two-sum (1-based indices). */
export function twoSumSorted(numbers: number[], target: number): number[] {
let lo = 0, hi = numbers.length - 1;
while (lo < hi) {
const sum = numbers[lo]! + numbers[hi]!;
if (sum === target) return [lo + 1, hi + 1];
if (sum < target) lo++;
else hi--;
}
throw new Error("No solution");
}
/** Two pointers template: sorted two-sum (1-based indices). */
export function twoSumSorted(numbers: number[], target: number): number[] {
let lo = 0, hi = numbers.length - 1;
while (lo < hi) {
const sum = numbers[lo]! + numbers[hi]!;
if (sum === target) return [lo + 1, hi + 1];
if (sum < target) lo++;
else hi--;
}
throw new Error("No solution");
}
- 1#11 Container With Most WaterRehbermedium
- 2#15 3SumRehbermedium
- 3#16 3Sum ClosestRehbermedium
- 4#18 4SumRehbermedium
- 5#42 Trapping Rain WaterRehberhard
- 6#167 Two Sum II. Input Array Is SortedRehbermedium