Two Sum
Adım 1/8
gereken—cevap—
nums · hedef 240
90
40
200
150
görülen — değer → indeks
—
—
—
—
idx 0
idx 1
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