İçeriğe atla
ΣDSA Patterns
Menü
KalıplarProblemlerŞablonlarYol haritasıKaynaklarMatematikTekrarlarHakkında
Dil
EnglishTürkçe

Önek Toplam

Rehber 3 / 6 · Yol 3 / 6

← ÖncekiSonraki →

Etkileşimli

Zihinsel model

Bu problem için animasyonlu çözüm. Adımları kaydır veya boşlukla duraklat; değişmezi yüksek sesle yeniden anlat.

Adım 1 / 6
1
1
1
eşlem0→1

k = 2

[1,1,1] üzerinde alt dizi toplamı k=2. pref−k daha önce görüldüyse say.

Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumprefix-sum

Subarray Sum Equals K

Problem (yeniden ifade)

Tamsayı dizisi nums (negatif olabilir) ve k verilir. Toplamı tam k olan bitişik alt dizi sayısını döndür. Aynı aralık bir kez sayılır.

Sezgi

Önek toplamları: (pref - k) kaç kez görülmüş say. Her böyle önceki önek, burada biten geçerli bir alt dizi oluşturur.

Yaklaşımlar

Önek toplam + hash map

Doğrulanmadı
Zaman O(n)Alan O(n)

Fikir. count[0]=1. Diziyi yürüyerek pref güncelle; ans += count[pref-k]; count[pref]++.

Yürüyüş. nums=[1,1,1], k=2 → alt diziler [1,1] iki kez → cevap 2.

Trade-off. Negatifleri işler (kayar pencere işlemez). count[0]=1 tohumlanmalı.

Çözüm
export function subarraySum(nums: number[], k: number): number {
  const count = new Map<number, number>([[0, 1]]);
  let pref = 0, ans = 0;
  for (const x of nums) {
    pref += x;
    ans += count.get(pref - k) ?? 0;
    count.set(pref, (count.get(pref) ?? 0) + 1);
  }
  return ans;
}

export function subarraySum(nums: number[], k: number): number {
  const count = new Map<number, number>([[0, 1]]);
  let pref = 0, ans = 0;
  for (const x of nums) {
    pref += x;
    ans += count.get(pref - k) ?? 0;
    count.set(pref, (count.get(pref) ?? 0) + 1);
  }
  return ans;
}

Şablon bağlantısı

Prefix Sum şablonundan önek toplam + hashmap.

Yansıma