Variabelt fönster med två pekare
Utöka och krymp för att uppfylla ett villkor
Variabelt fönster med två pekare är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 2 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
När fönstret växer och krymper
I vissa problem är fönstrets längd inte fast. I stället växer och krymper fönstret för att hålla ett villkor uppfyllt, till exempel att en summa ska ligga under en gräns.
Två pekare, ett fönster
Håll reda på två index, left och right, som markerar fönstrets kanter. Den högra pekaren utökar fönstret medan left följer efter och krymper det vid behov.
left = 0
window = 0Utöka åt höger
Gå åt höger över varje element och inkludera det i fönstret. Uppdatera ditt löpande tillstånd, till exempel genom att lägga till det nya värdet i en summa.
for right in range(n):
window += a[right]Krymp när det behövs
Så länge fönstret överträder regeln flyttar du left åt höger och tar bort det elementet. Då återställs villkoret utan att du behöver gå bakåt.
while window > limit:
window -= a[left]
left += 1Läs av det giltiga fönstret
När den inre loopen är klar är fönstret från left till right giltigt. Dess längd är right minus left plus one och kan användas direkt.
length = right - left + 1Spara det bästa
Uppdatera svaret med detta giltiga fönster, ofta det längsta du har sett. Gör det vid varje iteration så att inget missas.
best = max(best, right - left + 1)Därför är det linjärt
Varje pekare rör sig bara framåt, aldrig bakåt. left och right flyttas tillsammans högst n steg, så hela genomgången är O(n).
Kravet på monotonicitet
Detta fungerar när en utökning av fönstret bara gör villkoret svårare att uppfylla. Det är denna monotona egenskap som gör att left aldrig behöver gå bakåt.
Längsta kontra kortaste
För det kortaste giltiga fönstret krymper du så länge regeln fortfarande gäller och sparar resultatet innan du avbryter. Pekarnas mekanik är densamma.
while window >= target:
best = min(best, right - left + 1)
window -= a[left]
left += 1Se upp med tomma fönster
Om krympningen kan tömma fönstret måste du förhindra att left passerar right. Kontrollera också att ett svar faktiskt hittades innan du returnerar det.
Känn igen mönstret
Välj ett varierande fönster när ett problem frågar efter den längsta eller kortaste sammanhängande delen som uppfyller ett villkor för sina element.
Snabb kontroll
Du kör ett variabelt fönster med två pekare över en array med storleken n.
Sammanfattning
Utöka right för att inkludera element, krymp left så länge regeln bryts och spara varje giltigt fönster. Pekare som bara rör sig framåt håller tidskomplexiteten på O(n). ✅
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Variabelt fönster med två pekare” gratis?
Ja – hela texten till ”Variabelt fönster med två pekare” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Variabelt fönster med två pekare”?
Utöka och krymp för att uppfylla ett villkor Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 2 av 4.
Hur lång tid tar lektionen ”Variabelt fönster med två pekare”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Summor i fönster med fast storlek
- Variabelt fönster med två pekare
- Längsta delsträng utan upprepningar
- Räkna fönster som uppfyller en regel