Een paar met een gegeven som vinden
De brute force van O(n^2) verslaan
Een paar met een gegeven som vinden is een gratis Voorbereiding op programmeerinterviews-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 Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Het probleem van twee sommanden
Gegeven een array en een doelwaarde: vind twee waarden die samen de doelwaarde vormen. Dit is een van de meest voorkomende opgaven om mee op te warmen bij programmeerwedstrijden. 🔍
De brutekrachtmethode
De voor de hand liggende aanpak probeert elk paar met twee geneste lussen. Dat werkt, maar alle paren controleren kost O(n^2) en kan veel te traag zijn.
for i in range(n):
for j in range(i + 1, n):
if a[i] + a[j] == target:
return (i, j)Waar brute force vastloopt
Bij n rond 100000 betekent O(n^2) tien miljard controles en krijg je een TLE. De beperkingen vertellen je dat je iets snellers moet vinden.
Sorteren en daarna doorlopen
Als je de array eerst sorteert, lossen twee pointers vanaf beide uiteinden het probleem in één doorgang op. Sorteren kost O(n log n), daarna kost de doorloop O(n).
a.sort()
left, right = 0, len(a) - 1Vergelijken met de doelwaarde
Lees bij elke stap a[left] + a[right]. Dat ene getal bepaalt je volgende stap, zonder dat je hoeft te gokken.
total = a[left] + a[right]Exacte overeenkomst: klaar
Als de som gelijk is aan de doelwaarde, heb je het paar gevonden. Geef het meteen terug, want je hebt maar één geldig antwoord nodig.
if total == target:
return (left, right)Anders pas je aan
Als de som te klein is, verplaats je left naar rechts; als de som te groot is, verplaats je right naar links. De gesorteerde volgorde garandeert dat elke stap helpt.
elif total < target:
left += 1
else:
right -= 1Er bestaat geen paar
Als de pointers elkaar kruisen zonder overeenkomst, bestaat er geen geldig paar. Het einde van de lus is op zichzelf al een volledig antwoord.
Het alternatief met een hashset
Als je de oorspronkelijke indices moet behouden, is een hashset overzichtelijker: controleer voor elke waarde of de doelwaarde min die waarde al eerder is gezien.
seen = set()
for x in a:
if target - x in seen:
# found
pass
seen.add(x)Je methode kiezen
Gebruik twee pointers wanneer de array al gesorteerd is of kan worden gesorteerd. Gebruik een hashset wanneer je echte O(n) zonder sorteren nodig hebt of de indices moet behouden.
Let op duplicaten
Als een waarde met zichzelf een paar kan vormen, zorg er dan voor dat je twee indices verschillend zijn. Een snelle controle met left != right of i != j voorkomt die valkuil.
Korte controle
Je wilt de brutekrachtmethode van O(n^2) voor het vinden van een paar met een bepaalde som verbeteren.
Samenvatting
Sorteer en doorloop daarna met twee pointers om in O(n log n) een paar voor een doelwaarde te vinden, of gebruik een hashset voor O(n) wanneer indices belangrijk zijn. Kies op basis van de beperkingen. ✅
Leer Voorbereiding op programmeerinterviews 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
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Een paar met een gegeven som vinden” gratis?
Ja — de volledige tekst van “Een paar met een gegeven som vinden” 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 Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Een paar met een gegeven som vinden”?
De brute force van O(n^2) verslaan Je oefent met Voorbereiding op programmeerinterviews 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 Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews 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 “Een paar met een gegeven som vinden”?
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 Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews 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
- Twee pointers in een gesorteerde array
- Een paar met een gegeven som vinden
- Duplicaten ter plaatse verwijderen
- Twee gesorteerde reeksen samenvoegen