Summer i vinduer med fast størrelse

Mange oppgaver ber deg finne summen av hver blokk med k sammenhengende elementer. Det er unødvendig å beregne hver blokk fra grunnen av, og du kan gjøre det mer effektivt. 🪟

Den naive ideen er å summere hvert vindu med lengde k separat. Da gjentar du arbeid, og tidskompleksiteten blir O(n ganger k), noe som er for tregt for store inndata.

Nabo-vinduer overlapper nesten fullstendig. Når du flytter vinduet ett steg mot høyre, fjerner du bare elementet lengst til venstre og legger til ett nytt element på høyre side.

Begynn med å summere de første k elementene én gang. Denne ene summen er utgangspunktet du fortsetter å oppdatere når vinduet skyves fremover.

For å flytte vinduet må du legge til elementet som kommer inn, og trekke fra elementet som går ut. Da krever hvert steg konstant arbeid, O(1).

Etter hvert skyv oppdaterer du det du trenger, for eksempel den største vindussummen du har sett så langt. Verdien for vinduet er alltid tilgjengelig umiddelbart.

Du berører hvert element én gang for å legge det til og én gang til for å fjerne det, så hele gjennomgangen er O(n). Det håndterer store begrensninger uten problemer.

Elementet som forlater vinduet, er a[i - k], ikke a[i - 1]. Å få dette forskyvningen riktig er den vanligste feilen med vinduer med fast størrelse.

Trenger du det største gjennomsnittet for et vindu i stedet for summen? Bare del den sporede vindussummen på k. Selve logikken for skyvevinduet endres ikke.

Hvis arrayet er kortere enn k, finnes det ikke noe komplett vindu. Sammenlign len(a) med k på forhånd, og avslutt tidlig for å unngå en indeksfeil.

Bruk dette mønsteret når vinduslengden er fast og du kan kombinere verdier effektivt, for eksempel summer, antall eller enkel løpende statistikk.

Initialiser det første vinduet én gang, og legg til og trekk fra ved hvert steg for å skyve det i O(1). Hele gjennomgangen av et vindu med fast størrelse tar lineær tid. ✅