To pekere i en sortert array

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). 🎯

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.

Start én peker ved den venstre enden og én ved den høyre enden. De peker mot hverandre og lukker gradvis avstanden mellom seg.

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.

Fortsett løkken så lenge left < right. Når pekerne møtes eller krysser hverandre, er alle nyttige par kontrollert, og du kan stoppe.

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.

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.

Hvis summen er større enn målet, trenger du mindre. Flytt høyre peker mot venstre, mot mindre verdier, for å redusere totalsummen.

Hver bevegelse eliminerer en hel gruppe par som du ikke trenger å teste. Derfor blir gjennomgangen lineær i stedet for kvadratisk.

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.

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.

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. 🚀