İçeriğe geç

İki pointer

Ders 2 / 14 · 5 dk

İki pointer

Adım 1/9

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 -= 1

Mini quiz

1 / 3

Sıralı girdide iki pointer, O(n²) süren çift aramasını neye indirir?