Sommen van vensters met vaste grootte

Veel taken vragen om de som van elk blok van k opeenvolgende elementen. Elk blok opnieuw vanaf nul berekenen is verspilling, en het kan efficiënter. 🪟

Het naïeve idee telt elk venster van lengte k afzonderlijk op. Daardoor doe je werk steeds opnieuw en kost het O(n maal k), wat te traag is voor grote invoer.

Omliggende vensters overlappen bijna volledig. Als je één stap naar rechts gaat, verwijder je alleen het meest linkse element en voeg je rechts één nieuw element toe.

Begin door de eerste k elementen één keer op te tellen. Deze ene som vormt de basis die je blijft bijwerken terwijl het venster vooruit schuift.

Tel het binnenkomende element op en trek het vertrekkende element af. Zo blijft elke stap beperkt tot een constante hoeveelheid werk van O(1).

Werk na elke verschuiving bij wat je nodig hebt, bijvoorbeeld de maximumsom van een venster die je tot nu toe hebt gezien. De waarde van het venster is altijd direct beschikbaar.

Je raakt elk element één keer aan om het op te tellen en nog één keer om het te verwijderen, dus de volledige doorloop is O(n). Daarmee voldoe je gemakkelijk aan grote invoergrenzen.

Het element dat het venster verlaat is a[i - k], niet a[i - 1]. Deze verschuiving goed instellen is de meest voorkomende fout bij vaste vensters.

Heb je het grootste gemiddelde van een venster nodig in plaats van de som? Deel de bijgehouden venstersom gewoon door k. De schuiflogica verandert helemaal niet.

Als de array korter is dan k, bestaat er geen volledig venster. Vergelijk vooraf len(a) met k en geef meteen een resultaat terug om een indexfout te voorkomen.

Gebruik dit patroon wanneer de lengte vaststaat en je waarden goedkoop combineert, zoals bij sommen, tellingen of eenvoudige lopende statistieken.

Initialiseer het eerste venster één keer en tel op en trek af bij elke stap om het in O(1) te verschuiven. De volledige doorloop met vaste grootte werkt in lineaire tijd. ✅