İki pointer
Adım 1/9
hedef15toplam—
left
right
1
3
4
8
11
15
012345
Dizi sıralı; o yüzden en geniş aralıkla başla: her uçta bir pointer.
Fikir
Her uçta bir indeks tut ve gördüğüne göre ikisini birbirine doğru ilerlet. Her adım, bir grup çifti tek seferde eler. Brute force (kaba kuvvet) her çifti O(n²) sürede kontrol eder; iki pointer (two pointers) aynı işi O(n)'de yapar.
Gerçek hayattan örnek
İki kişi uzun bir kitaplıkta birbirine uyan iki cildi arıyor; biri bir uçtan, diğeri öbür uçtan başlayıp içeri doğru yürüyor. Ortada buluştuklarında rafı tam bir kez taramış oluyorlar; birinin her kitap için rafı baştan dolaşmasına gerek kalmıyor.
Kod
Sıra sende
Bu kod ne yazdırır?
nums = [2, 5, 9]
l, r = 0, 2
while l < r:
print(nums[l] + nums[r])
l += 1
r -= 1Mini quiz
1 / 3