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 Sums Divisible by K

Problem (yeniden ifade)

Tamsayı dizisi nums ve k verilir. Toplamı k’ya tam bölünen, boş olmayan bitişik alt dizi sayısını döndür. nums negatif olabilir.

Sezgi

Önek toplamların aynı kalanı ⇒ aradaki toplam k’ya bölünür.

Yaklaşımlar

Önek mod sayıları

Doğrulanmadı

Zaman O(n)Alan O(k)

Fikir. Her önek mod’unun sıklığını say; her yeni mod r için count[r] ekle, sonra artır.

Yürüyüş. [4,5,0,-2,-3,1], k=5 → 7.

Trade-off. Negatif kalan veren dillerde negatif mod’ları normalize et.

Çözüm

export function subarraysDivByK(nums: number[], k: number): number {
  const cnt = new Array<number>(k).fill(0);
  cnt[0] = 1;
  let sum = 0, ans = 0;
  for (const x of nums) {
    sum += x;
    const r = ((sum % k) + k) % k;
    ans += cnt[r]!;
    cnt[r]!++;
  }
  return ans;
}

export function subarraysDivByK(nums: number[], k: number): number {
  const cnt = new Array<number>(k).fill(0);
  cnt[0] = 1;
  let sum = 0, ans = 0;
  for (const x of nums) {
    sum += x;
    const r = ((sum % k) + k) % k;
    ans += cnt[r]!;
    cnt[r]!++;
  }
  return ans;
}

Şablon bağlantısı

prefix mod k; kalan frekanslarını say (523 / 930 ailesi).

Yansıma

pref % k aynı olan önceki önekler. Negatif nums: Python vs C#/TS mod. ((pref % k) + k) % k.
Boş önek mod 0 bir kez tohumlanır. Alt dizi boş olamaz — tohum bunu nasıl saymaz?
k = 1: her alt dizi geçerli, cevap n(n+1)/2.