Verilen Toplama Sahip Bir Çift Bulma
O(n^2) kaba kuvvet yaklaşımını geride bırakın.
Verilen Toplama Sahip Bir Çift Bulma, CoddyKit'te ücretsiz bir Competitive Programming Academy dersidir. Bu, 4 dersinin 2. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Competitive Programming Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Competitive Programming Academy kursu toplamda 4 dersten oluşur.
İki Sayının Toplamı Problemi
Bir dizi ve bir hedef verildiğinde, toplamı hedefe eşit olan iki değer bulun. Bu, yarışmalardaki en yaygın başlangıç görevlerinden biridir. 🔍
Kaba Kuvvet Yöntemi
Açık çözüm, iç içe iki döngüyle her çifti dener. Çalışır, ancak tüm çiftleri kontrol etmek O(n^2) maliyetindedir ve fazlasıyla yavaş olabilir.
for i in range(n):
for j in range(i + 1, n):
if a[i] + a[j] == target:
return (i, j)Kaba Kuvvetin Yetersiz Kaldığı Yer
n değeri 100000'e yaklaştığında O(n^2), on milyar kontrol demektir ve TLE alırsınız. Kısıtlar size daha hızlı bir çözüm bulmanız gerektiğini gösterir.
Sırala, Sonra Tara
Diziyi önce sort ederseniz, iki uçtan başlayan iki işaretçi sorunu tek geçişte çözer. Sıralama O(n log n) maliyetindedir; ardından tarama O(n) sürer.
a.sort()
left, right = 0, len(a) - 1Hedefle Karşılaştırma
Her adımda a[left] + a[right] ifadesini okuyun. Bu tek sayı, tahmine gerek bırakmadan bir sonraki hareketinizi belirler.
total = a[left] + a[right]Tam Eşleşme: Bitti
Toplam hedefe eşitse çifti bulmuşsunuzdur. Yalnızca bir geçerli yanıt gerektiğinden hemen döndürün.
if total == target:
return (left, right)Değilse Ayarlayın
Toplam çok küçükse sol işaretçiyi sağa, çok büyükse sağ işaretçiyi sola ilerletin. Sıralı düzen her hareketin yardımcı olacağını garanti eder.
elif total < target:
left += 1
else:
right -= 1Çift Yok
İşaretçiler eşleşme olmadan birbirini geçerse, geçerli bir çift yoktur. Döngünün sona ermesi tek başına eksiksiz bir yanıttır.
Karma Kümesi Seçeneği
özgün indeksleri korumanız gerekiyorsa karma kümesi daha düzenli bir çözümdür: her değer için, hedef eksi değerin daha önce görülüp görülmediğini kontrol edin.
seen = set()
for x in a:
if target - x in seen:
# found
pass
seen.add(x)Yönteminizi Seçme
Dizi sıralıysa veya sıralanabiliyorsa iki işaretçi kullanın; sıralama yapmadan gerçek O(n) süresine ihtiyaç duyuyorsanız ya da indeksleri korumanız gerekiyorsa karma kümesini kullanın.
Yinelenen Değerlere Dikkat Edin
Bir değer kendisiyle eşleşebiliyorsa, iki indeksinizin farklı olduğundan emin olun. Hızlı bir left != right veya i != j kontrolü bu tuzağı önler.
Hızlı Kontrol
Hedefe toplamı eşit olan bir çift bulurken O(n^2) kaba kuvvet çözümünden daha iyi bir yöntem istiyorsunuz.
Özet
Hedefe uygun bir çifti O(n log n) sürede bulmak için iki işaretçiyle sıralayın ve tarayın; indeksler önemliyse O(n) için karma kümesi kullanın. Kısıtlara göre seçim yapın. ✅
Sıkça Sorulan Sorular
“Verilen Toplama Sahip Bir Çift Bulma” dersi ücretsiz mi?
Evet — “Verilen Toplama Sahip Bir Çift Bulma” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Competitive Programming Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Competitive Programming Academy kursu toplamda 4 dersten oluşur.
“Verilen Toplama Sahip Bir Çift Bulma” dersinde ne öğreneceğim?
O(n^2) kaba kuvvet yaklaşımını geride bırakın. Competitive Programming Academy ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Competitive Programming Academy öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Competitive Programming Academy, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 2. dersidir.
“Verilen Toplama Sahip Bir Çift Bulma” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Competitive Programming Academy dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Competitive Programming Academy dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Sıralanmış Dizide İki İşaretçi
- Verilen Toplama Sahip Bir Çift Bulma
- Yinelenenleri Yerinde Kaldırma
- İki Sıralı Diziyi Birleştirme