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

Binary Subarrays With Sum

Problem (yeniden ifade)

İkili dizi ve goal verilir; toplamı == goal olan boş olmayan alt dizi sayısını döndür.

Sezgi

Klasik prefix-count: her prefix S için S-goal’a eşit prefix sayısını ekle.

Yaklaşımlar

Önek toplam hash

Doğrulanmadı

Zaman O(n)Alan O(n)

Fikir. prefix→count map; prefix 0’ı count 1 ile başlat; cevapları biriktir.

Yürüyüş. [1,0,1,0,1], goal=2 → 4 alt dizi.

Trade-off. Sliding window atMost(goal)-atMost(goal-1) ikili dizilerde de çalışır.

Çözüm

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

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

Şablon bağlantısı

Binary alt diziler için önek-toplam hash (veya atMost(goal) − atMost(goal-1)).

Yansıma

İkili dizi + tam toplam → “en fazla goal” eksi “en fazla goal-1”. Neden doğrudan eşitlik penceresi zor?
Önek + hash de çalışır; kayan pencere burada neden O(1) bellek?
goal = 0: yalnızca sıfır koşuları.