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

Mediumsliding-window

Minimum Size Subarray Sum

Problem (yeniden ifade)

Pozitif tamsayı dizisi nums ve pozitif tamsayı target verildiğinde, toplamı ≥ target olan bitişik bir alt dizinin minimal uzunluğunu döndür. Böyle alt dizi yoksa 0 döndür.

Sezgi

Tüm değerler pozitif olduğu için sağ ucu genişletmek toplamı yalnızca artırır, solu daraltmak yalnızca azaltır. Klasik değişken pencere.

Yaklaşımlar

Kayan pencere

Doğrulanmadı

Zaman O(n)Alan O(1)

Fikir. sum < target iken right’ı büyüt. sum ≥ target olunca left’i olabildiğince daralt ve min uzunluğu izle.

Yürüyüş. nums=[2,3,1,2,4,3], target=7. Pencere [2,3,1,2] sum=8’e büyür → uzunluk 4. [3,1,2] sonra [1,2,4]… olacak şekilde daralır; sonunda [4,3] uzunluk 2.

Trade-off. Optimal doğrusal tarama. Prefix toplamlarında ikili arama O(n log n) ve yalnızca negatifler varsa gerekir (burada yok).

Çözüm

export function minSubArrayLen(target: number, nums: number[]): number {
  let left = 0, sum = 0, best = Infinity;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right]!;
    while (sum >= target) {
      best = Math.min(best, right - left + 1);
      sum -= nums[left++]!;
    }
  }
  return best === Infinity ? 0 : best;
}

export function minSubArrayLen(target: number, nums: number[]): number {
  let left = 0, sum = 0, best = Infinity;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right]!;
    while (sum >= target) {
      best = Math.min(best, right - left + 1);
      sum -= nums[left++]!;
    }
  }
  return best === Infinity ? 0 : best;
}

Şablon bağlantısı

Sliding window: sağı büyüt, sum ≥ target iken solu küçült, min uzunluğu tut.

Yansıma

Tüm değerler pozitifken sağı büyütmenin toplamı yalnızca artırması pencereyi nasıl seçtirir?
sum ≥ target iken solu olabildiğince daraltmazsan cevap neden büyük kalır?
Negatif eklenirse aynı tarama neden kırılır? (O zaman önek + ikili arama.)