Due puntatori su un array ordinato
Spostare le estremità verso il centro per raggiungere un obiettivo
Due puntatori su un array ordinato è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Perché usare due puntatori
La tecnica dei due puntatori attraversa un array con due indici invece di usare cicli annidati, trasformando molte soluzioni O(n^2) in un'unica scansione lineare O(n). 🎯
Ordinato è la parola magica
La versione classica richiede un array ordinato. L'ordine permette di ragionare: spostarsi verso destra aumenta il valore, verso sinistra lo diminuisce, quindi ogni passo è una scelta effettiva.
Due puntatori alle estremità
Si posiziona un puntatore all'estremità left e uno all'estremità right. I due puntatori si fronteggiano e riducono lentamente la distanza tra loro.
left = 0
right = len(a) - 1Spostare le estremità verso l'interno
A ogni passaggio si sposta esattamente un puntatore verso l'interno. L'ordine dell'array indica quale lato spostare per avvicinarsi all'obiettivo.
La condizione del ciclo
Si continua il ciclo finché left < right. Quando i puntatori si incontrano o si oltrepassano, ogni coppia utile è stata verificata e ci si può fermare.
while left < right:
# inspect a[left] and a[right]
passLeggere la somma corrente
Si consideri a[left] + a[right] come candidato corrente. Confrontarlo con un target indica se occorre cercare un valore maggiore o minore.
total = a[left] + a[right]Troppo piccola: spostare left
Se la somma è inferiore al target, ne serve di più. Si sposta il puntatore left verso destra, in direzione dei valori maggiori, poiché l'array è ordinato in modo crescente.
if total < target:
left += 1Troppo grande: spostare right
Se la somma è superiore al target, ne serve di meno. Si sposta il puntatore right verso sinistra, in direzione dei valori minori, per ridurre il totale.
elif total > target:
right -= 1Ogni passaggio elimina del lavoro
Ogni spostamento elimina un intero gruppo di coppie che non è necessario verificare. Ecco perché la scansione è lineare invece che quadratica.
Perché rimane corretto
Si scartano solo le coppie che non possono corrispondere, quindi la risposta corretta non viene mai saltata. È questa sicurezza a rendere affidabile la tecnica dei due puntatori nelle gare.
Oltre le estremità
La stessa idea è alla base di diverse varianti: inversione sul posto, partizionamento e fusione. Una volta compreso il funzionamento dei puntatori che si incontrano, tutte queste tecniche risultano familiari.
Verifica rapida
Si sta scorrendo un array ordinato da entrambe le estremità alla ricerca di una somma target.
Riepilogo
Due puntatori attraversano un array ordinato da entrambe le estremità, spostandone uno verso l'interno a ogni passaggio finché left < right. È una tecnica lineare e corretta, alla base di molti altri trucchi. 🚀
Domande Frequenti
La lezione «Due puntatori su un array ordinato» è gratuita?
Sì — il testo completo di «Due puntatori su un array ordinato» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Due puntatori su un array ordinato»?
Spostare le estremità verso il centro per raggiungere un obiettivo Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Due puntatori su un array ordinato»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Due puntatori su un array ordinato
- Trovare una coppia con una somma data
- Rimuovere i duplicati sul posto
- Unire due sequenze ordinate