İçeriğe geç

Two Sum

Ders 2 / 8 · 5 dk

Two Sum

Adım 1/8

Her çifti kontrol etmek O(n²). Bunun yerine bir kez dolaş ve geçenleri hatırla.

Fikir

Her çifti karşılaştırmak O(n²) tutar. Bunun yerine listeyi bir kez dolaş ve görülen değerleri tutan bir hash map'e tek bir soru sor: tamamlayıcı — hedef eksi bu değer — daha önce geçti mi? Hash map'ten bir okuma anında cevap verir; tek geçiş işi bitirir.

Gerçek hayattan örnek

Bir nalbur, kereste artıklarını bir kutuda tutuyor ve bir müşterinin iki parçadan tam 240 cm'ye ihtiyacı var. Görevli her artığı bir kez ölçüp boyunu bir deftere yazıyor; her ölçümden sonra kutuyu yeniden aramak yerine eksik kalan boy için deftere göz atıyor.

Kod

Sıra sende

Boşluğu doldur.

def two_sum(nums, target):
  seen = {}
  for i, x in enumerate(nums):
      if ___ in seen:
          return (seen[target - x], i)
      seen[x] = i

print(two_sum([90, 40, 200, 40], 240))   # want (1, 2)

Mini quiz

1 / 3

Hash map'li Two Sum çözümünün zaman karmaşıklığı nedir?