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

Continuous Subarray Sum

Problem (yeniden ifade)

nums içinde toplamı k’nın katı olan, uzunluğu ≥ 2 bitişik bir alt dizi varsa true döndür.

Sezgi

İki önek toplamı aynı mod k’yı paylaşıyorsa, aradaki toplam k’nın katıdır; indeks farkı ≥ 2 gerekir.

Yaklaşımlar

Önek mod haritası

Doğrulanmadı

Zaman O(n)Alan O(min(n,k))

Fikir. Kalan → en erken indeks map’i. j-i≥2 ile tekrar olursa true.

Yürüyüş. [23,2,4,6,7], k=6 → alt dizi [2,4] çalışır.

Trade-off. k=0 kenarına dikkat (kısıtlarda genelde k>0).

Çözüm

export function checkSubarraySum(nums: number[], k: number): boolean {
  const seen = new Map<number, number>([[0, -1]]);
  let sum = 0;
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i]!;
    const r = k === 0 ? sum : ((sum % k) + k) % k;
    if (seen.has(r)) { if (i - seen.get(r)! >= 2) return true; }
    else seen.set(r, i);
  }
  return false;
}

export function checkSubarraySum(nums: number[], k: number): boolean {
  const seen = new Map<number, number>([[0, -1]]);
  let sum = 0;
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i]!;
    const r = k === 0 ? sum : ((sum % k) + k) % k;
    if (seen.has(r)) { if (i - seen.get(r)! >= 2) return true; }
    else seen.set(r, i);
  }
  return false;
}

Şablon bağlantısı

prefix mod k; tekrarlayan kalan, k’ya bölünen bir alt dizi toplamı demektir (uzunluk ≥ 2).

Yansıma

Toplamın k katı, uzunluk ≥ 2. pref % k aynı ve indeks farkı ≥ 2. Neden ham toplam değil mod?
k = 0 / negatif k. Python % işareti. İlk görülen indeksi mi, sayacı mı saklarsın?
Tek eleman k’nın katı: uzunluk 1 yasal değil.