To pekere i en sortert array
Flytt endene innover for å treffe et mål
To pekere i en sortert array er en gratis leksjon i Competitive Programming Academy på CoddyKit. Dette er leksjon 1 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Competitive Programming Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Hvorfor to pekere
Teknikken med to pekere går gjennom et array med to indekser i stedet for nøstede løkker, og gjør mange O(n^2)-løsninger om til én ryddig gjennomgang på O(n). 🎯
Sortert er nøkkelordet
Den klassiske varianten krever et sortert array. Rekkefølgen gjør det mulig å resonnere: Når du går mot høyre, øker verdien, og når du går mot venstre, synker den, så hvert trinn er et reelt valg.
To pekere i endene
Start én peker ved den venstre enden og én ved den høyre enden. De peker mot hverandre og lukker gradvis avstanden mellom seg.
left = 0
right = len(a) - 1Flytt endene innover
På hvert trinn flytter du nøyaktig én peker innover. Rekkefølgen i arrayet forteller hvilken side du skal justere for å komme nærmere målet.
Løkkebetingelsen
Fortsett løkken så lenge left < right. Når pekerne møtes eller krysser hverandre, er alle nyttige par kontrollert, og du kan stoppe.
while left < right:
# inspect a[left] and a[right]
passLes av den aktuelle summen
Se på a[left] + a[right] som den aktuelle kandidaten. Når du sammenligner den med et mål, ser du om neste verdi må være større eller mindre.
total = a[left] + a[right]For liten: Flytt venstre peker
Hvis summen er mindre enn målet, trenger du mer. Flytt venstre peker mot høyre, mot større verdier, siden arrayet er sortert stigende.
if total < target:
left += 1For stor: Flytt høyre peker
Hvis summen er større enn målet, trenger du mindre. Flytt høyre peker mot venstre, mot mindre verdier, for å redusere totalsummen.
elif total > target:
right -= 1Hvert trinn forkaster arbeid
Hver bevegelse eliminerer en hel gruppe par som du ikke trenger å teste. Derfor blir gjennomgangen lineær i stedet for kvadratisk.
Hvorfor metoden er korrekt
Du forkaster bare par som ikke kan passe, så det riktige svaret blir aldri hoppet over. Denne sikkerheten gjør to pekere pålitelige i konkurranser.
Mer enn endepunktene
Den samme ideen brukes i varianter som reversering på stedet, partisjonering og fletting. Når du behersker pekere som møtes, vil alle disse føles kjente.
Kort kontroll
Du går gjennom et sortert array fra begge ender for å finne en bestemt sum.
Oppsummering
To pekere går gjennom et sortert array fra begge ender og flytter én peker innover på hvert trinn mens left < right. Lineært, korrekt og grunnlaget for mange triks. 🚀
Lær deg Python med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 30
- Leksjoner
- 120
Ofte stilte spørsmål
Er leksjonen «To pekere i en sortert array» gratis?
Ja – hele teksten i «To pekere i en sortert array» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Competitive Programming Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Hva lærer jeg i «To pekere i en sortert array»?
Flytt endene innover for å treffe et mål Du øver på Competitive Programming Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Competitive Programming Academy?
Ingen tidligere erfaring er nødvendig. Competitive Programming Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.
Hvor lang tid tar leksjonen «To pekere i en sortert array»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Competitive Programming Academy-leksjonen?
Ja. Alle Competitive Programming Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- To pekere i en sortert array
- Finn et par med en gitt sum
- Fjern duplikater på stedet
- Slå sammen to sorterte sekvenser