Variabel venster met twee pointers
Vergroten en verkleinen om aan een voorwaarde te voldoen
Variabel venster met twee pointers is een gratis Competitive Programming Academy-les op CoddyKit. Dit is les 2 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Competitive Programming Academy. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Wanneer het venster groeit en krimpt
Sommige problemen leggen de vensterlengte niet vast. In plaats daarvan groeit en krimpt het venster om een voorwaarde waar te houden, bijvoorbeeld dat een som onder een limiet blijft.
Twee aanwijzers, één venster
Houd twee indices bij, left en right, die de randen van het venster aangeven. De aanwijzer right breidt uit, terwijl left erachteraan komt om het venster zo nodig te verkleinen.
left = 0
window = 0Breid naar rechts uit
Loop met right over elk element en neem het op in het venster. Werk je lopende toestand bij, bijvoorbeeld door de nieuwe waarde bij een som op te tellen.
for right in range(n):
window += a[right]Verklein wanneer nodig
Zolang het venster de regel schendt, verplaats je left naar rechts en verwijder je dat element. Zo herstel je de voorwaarde zonder terug te gaan.
while window > limit:
window -= a[left]
left += 1Lees het geldige venster
Zodra de binnenste lus eindigt, is het venster van left tot right geldig. De lengte is right min left plus één en kan direct worden gebruikt.
length = right - left + 1Leg je beste vast
Werk je antwoord bij met dit geldige venster, vaak het langste dat je tot nu toe hebt gezien. Doe dit bij elke iteratie, zodat je niets mist.
best = max(best, right - left + 1)Waarom dit lineair is
Elke aanwijzer beweegt alleen vooruit en nooit terug. left en right gaan samen hoogstens n stappen vooruit, dus de volledige doorloop is O(n).
De monotone voorwaarde
Dit werkt wanneer het uitbreiden van het venster de voorwaarde alleen maar moeilijker maakt om aan te voldoen. Dankzij dat monotone gedrag hoeft left nooit terug te gaan.
Langste tegenover kortste
Voor het kortste geldige venster verklein je het zolang de regel nog geldt en leg je het vast voordat je stopt. De werking van de aanwijzers blijft hetzelfde.
while window >= target:
best = min(best, right - left + 1)
window -= a[left]
left += 1Let op lege vensters
Als verkleinen het venster leeg kan maken, voorkom dan dat left voorbij right gaat. Controleer ook of je daadwerkelijk een antwoord hebt gevonden voordat je het teruggeeft.
Het patroon herkennen
Kies een variabel venster wanneer een probleem vraagt om de langste of kortste aaneengesloten reeks die aan een voorwaarde voor de elementen voldoet.
Snelle controle
Je gebruikt een variabel venster met twee aanwijzers op een array van grootte n.
Samenvatting
Breid right uit om elementen op te nemen, verklein left zolang de regel wordt geschonden en leg elk geldig venster vast. Aanwijzers die alleen vooruitgaan houden de oplossing op O(n). ✅
Leer Python met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “Variabel venster met twee pointers” gratis?
Ja — de volledige tekst van “Variabel venster met twee pointers” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Competitive Programming Academy wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Wat leer ik in “Variabel venster met twee pointers”?
Vergroten en verkleinen om aan een voorwaarde te voldoen Je oefent met Competitive Programming Academy door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Competitive Programming Academy te beginnen?
Ervaring vooraf is niet nodig. Competitive Programming Academy op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 2 van 4.
Hoe lang duurt de les “Variabel venster met twee pointers”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Competitive Programming Academy?
Ja. Elke les over Competitive Programming Academy bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Sommen van vensters met vaste grootte
- Variabel venster met twee pointers
- Langste substring zonder herhalingen
- Vensters tellen die aan een regel voldoen