ENDEAR
Kostenlos starten
Algorithmusgratis

Sliding Window

Finde die größte Summe von k aufeinanderfolgenden Zahlen, ohne das Fenster jedes Mal neu aufzusummieren.

Zeit
O(n)
Speicher
O(1)

// Schritt für Schritt

Schritt 1 / 9
1function maxWindowSum(nums, k) {2  let total = 0;3  for (let i = 0; i < k; i++) total += nums[i];4  let best = total;5  for (let i = k; i < nums.length; i++) {6    total += nums[i] - nums[i - k];7    best = Math.max(best, total);8  }9  return best;10}
k
= 3
total
= 8
  1. 2
  2. 1
  3. 5
  4. 1
  5. 3
  6. 2

Summiere das erste Fenster aus k = 3 Zahlen: total = 8.

So funktioniert es

Summiere die ersten k Zahlen einmal. Dann schiebe das Fenster Schritt für Schritt weiter: Addiere die Zahl, die rechts hineinkommt, und ziehe die ab, die links herausfällt. Jedes Fenster kostet O(1), der ganze Durchlauf ist also linear.