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

Easyprefix-sum

Range Sum Query. Immutable

Problem (yeniden ifade)

Değişmez nums verilen, sumRange(left, right) sorularını verimli yanıtlayan bir yapı tasarla.

Sezgi

prefix[i] = ilk i elemanın toplamı; aralık = prefix[r+1]-prefix[l].

Yaklaşımlar

Önek toplamlar

Tested only

Time O(1) querySpace O(n)

Fikir. Öneki bir kez kur; her sorgu iki dizi erişimi.

Adım adım. nums=[-2,0,3,-5,2,-1]; sumRange(0,2)=1; sumRange(2,5)=-1.

Trade-off’lar. Yalnızca değişmez + aralık-toplamı için segment tree abartı.

Solution

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]!;
  }
}

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]!;
  }
}

Yansıma

Hangi ipucu bu kalıbı 90 saniyede seçtirdi?
Yanlış bir değişmezi hangi girdi bozardı?