Hedef Toplamlı Alt Dizileri Sayma
Önek toplamlarını bir karma tabloyla birleştirin.
Hedef Toplamlı Alt Dizileri Sayma, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 3. 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, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Daha Zor Bir Soru
Şimdi işin püf noktası şu: toplamı hedef k'ye eşit olan kaç alt dizi olduğunu sayın. Her ikiliyi denemek yavaştır; ancak prefix toplamları ve bir karma tablo bu sorunu çözer. 🎯
Prefix'lerle Yeniden Düşünün
Bir alt dizinin toplamı prefix[r + 1] eksi prefix[l] değerine eşittir. Dolayısıyla toplamın k olması, iki prefix değerinin tam olarak k kadar farklı olması demektir.
Temel Yeniden Düzenleme
Geçerli prefix değeri P ise, P eksi k'ye eşit daha önceki bir prefix değerine ihtiyacınız vardır. Bu yeniden düzenleme, yöntemin temel püf noktasıdır.
need = current_prefix - kAramayın, Sayın
Her seferinde geriye doğru taramak yerine, her prefix değerinin kaç kez görüldüğünü hatırlayın. Devam eden bir sayım O(1) zamanda yanıt verir.
Frekans Tablosu Kullanın
Bir sözlük, her prefix değerini o değeri kaç kez gördüğünüzle eşleştirir. Bu tablo, aramayı anında yapılan bir sayma işlemine dönüştürür.
from collections import defaultdict
seen = defaultdict(int)Boş Prefix'i Başlatın
Döngüden önce prefix 0'ın bir kez görüldüğünü kaydedin. Bu başlangıç değeri, 0 dizininden başlayan alt dizilerin sayılmasını sağlar.
seen[0] = 1Tek Geçişli Döngü
Her öğe için devam eden prefix değerini güncelleyin, gereken değerin sayısını sonuca ekleyin, ardından geçerli prefix değerini kaydedin. Tek bir geçişte her şey tamamlanır.
total += x
count += seen[total - k]
seen[total] += 1Sıra Neden Önemli
Geçerli prefix değerini kaydetmeden önce sonucu güncellemelisiniz. Aksi hâlde sıfır uzunluklu bir aralık yanlışlıkla hesaba katılır ve sayım bozulur.
Hız Kazancı
Her öğe için sabit miktarda işlem yapıldığı için toplam sayma işlemi O(n) zamanda tamamlanır. Bu, büyük girdilerde O(n kare) şeklindeki kaba kuvvet yönteminden daha hızlıdır.
Negatif Sayılar da Olur
Kayan pencere yönteminin aksine bu yöntem negatif sayıları da sorunsuzca ele alır; çünkü prefix farkları işaretlerden bağımsız olarak geçerliliğini korur.
Klasik Bir Kullanım Alanı
Bu şablon, ünlü toplamı k'ye eşit alt dizi problemini ve yarışma değerlendirmelerinde karşılaşılan birçok gizli varyasyonu çözer.
Hızlı Kontrol
Devam eden prefix değeriniz P, hedef değeriniz ise k.
Özet
Prefix toplamlarını ve bir frekans tablosunu kullanarak hedef toplamlı alt dizileri O(n) zamanda sayabilirsiniz. Önce prefix 0'ı başlatın, sonra kaydetmeden önce sayın. ✅
Sıkça Sorulan Sorular
“Hedef Toplamlı Alt Dizileri Sayma” dersi ücretsiz mi?
Evet — “Hedef Toplamlı Alt Dizileri Sayma” 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 Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Hedef Toplamlı Alt Dizileri Sayma” dersinde ne öğreneceğim?
Önek toplamlarını bir karma tabloyla birleştirin. Coding Interview Prep 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.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, 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 3. dersidir.
“Hedef Toplamlı Alt Dizileri Sayma” 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 Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep 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
- Önek Toplam Dizisi Oluşturma
- Çıkarma ile Her Aralığı Toplama
- Hedef Toplamlı Alt Dizileri Sayma
- Aralık Güncellemeleri için Fark Dizileri