Kalıp #07
Önek Toplam
TemelÇalışan toplamları önceden hesapla; herhangi bir aralık toplamı O(1). Alt dizi toplam sayıları için map ile birleştir.
Ne zaman kullanılır
Çok sayıda aralık-toplam sorgusu veya toplamı hedefe eşit alt dizileri sayma/bulma (önek + hashmap).
Tanıma ipuçları
- Aralık toplam sorguları
- Alt dizi toplamı K'ya eşit
- Denge / pivot indeks
- Toplamı K olan ikili alt diziler (0/1 diziler)
Yaygın tuzaklar
- Dahil indeksler ile pref[i+1] arasında off-by-one
- k'ya toplarken boş önek için count[0] = 1 unutmak
- Sabit tamsayılı dillerde taşma (C#'ta long kullan)
90 saniyelik tanıma egzersizi
Hangisi en iyi uyuyor?
- Aralık toplam sorguları
- Alt dizi toplamı K'ya eşit
- Denge / pivot indeks
Interactive
Zihinsel model
Değişmezin tam adım adım anlatımı. Duraklat, noktalara tıkla veya ← → kullan. Her adımı kendi cümlelerinle anlatmayı hedefle.
pref = [0, ?, ?, ?, ?]
Build prefix with pref[0] = 0.
Nasıl düşünülür
pref bir kez kur ki her aralık tek çıkarma olsun: sum(i..j) = pref[j+1] - pref[i]. “Kaç alt dizi k’ya toplar” için her önekin kaç kez görüldüğünü izle: pref - k görüldüyse o önceki konumlar burada biten geçerli alt dizilerdir.
Karmaşıklık temeli
Önek kurmak O(n); her aralık sorgusu O(1). Sayım için hashmap varyantı O(n) zaman ve alan.
Şablon
TypeScript, Python ve C#’te aynı iskelet. Değişmezi uyarla; yapıyı koru.
/** Prefix sum template: O(1) range sum after O(n) build. */
export class NumArray {
private pref: number[];
constructor(nums: number[]) {
this.pref = new Array(nums.length + 1).fill(0);
for (let i = 0; i < nums.length; i++) this.pref[i + 1] = this.pref[i]! + nums[i]!;
}
sumRange(left: number, right: number): number {
return this.pref[right + 1]! - this.pref[left]!;
}
}
/** Prefix sum template: O(1) range sum after O(n) build. */
export class NumArray {
private pref: number[];
constructor(nums: number[]) {
this.pref = new Array(nums.length + 1).fill(0);
for (let i = 0; i < nums.length; i++) this.pref[i + 1] = this.pref[i]! + nums[i]!;
}
sumRange(left: number, right: number): number {
return this.pref[right + 1]! - this.pref[left]!;
}
}
- 1#303 Range Sum Query. ImmutableRehbereasy
- 2#523 Continuous Subarray SumRehbermedium
- 3#560 Subarray Sum Equals KRehbermedium
- 4#724 Find Pivot IndexRehbereasy
- 5#930 Binary Subarrays With SumRehbermedium
- 6#974 Subarray Sums Divisible by KRehbermedium