Finestra variabile con due puntatori
Espandere e restringere la finestra fino a soddisfare una condizione
Finestra variabile con due puntatori è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 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.
Quando la finestra varia
In alcuni problemi la lunghezza della finestra non è fissa. La finestra invece si espande e si restringe per mantenere vera una condizione, ad esempio una somma inferiore a un limite.
Due puntatori, una finestra
Mantenga due indici, left e right, che indicano i bordi della finestra. Il puntatore right la espande, mentre left lo segue e la restringe quando necessario.
left = 0
window = 0Espandere verso destra
Attraversi ogni elemento verso destra e lo includa nella finestra. Aggiorni lo stato corrente, ad esempio aggiungendo il nuovo valore a una somma.
for right in range(n):
window += a[right]Restringere quando necessario
Finché la finestra viola la regola, sposti left verso destra e rimuova quell'elemento. In questo modo ripristina la condizione senza tornare indietro.
while window > limit:
window -= a[left]
left += 1Leggere la finestra valida
Quando termina il ciclo interno, la finestra da left a right è valida. La sua lunghezza è right meno left più uno, pronta per essere utilizzata.
length = right - left + 1Memorizzare il risultato migliore
Aggiorni la risposta usando questa finestra valida, spesso quella più lunga incontrata finora. Lo faccia a ogni iterazione, così non perderà alcun caso.
best = max(best, right - left + 1)Perché è lineare
Ogni puntatore si muove solo in avanti, senza mai tornare indietro. Insieme, left e right avanzano al massimo di n posizioni, quindi l'intera scansione è O(n).
Il requisito di monotonicità
Questo approccio funziona quando estendere la finestra rende la condizione solo più difficile da soddisfare. È proprio questo comportamento monotono a permettere a left di non tornare mai indietro.
Più lunga o più corta
Per trovare la finestra valida più corta, la restringa finché la regola continua a essere rispettata e memorizzi il risultato prima di interrompere. La meccanica dei puntatori rimane la stessa.
while window >= target:
best = min(best, right - left + 1)
window -= a[left]
left += 1Attenzione alle finestre vuote
Se la finestra può diventare vuota restringendola, controlli che left non superi right. Verifichi inoltre di aver trovato effettivamente una risposta prima di restituirla.
Riconoscere lo schema
Scelga una finestra variabile quando il problema richiede il tratto contiguo più lungo o più corto che soddisfa una condizione sui suoi elementi.
Verifica rapida
Applica una finestra variabile con due puntatori a un array di dimensione n.
Riepilogo
Espanda right per includere gli elementi, restringa left quando la regola viene violata e memorizzi ogni finestra valida. I puntatori che avanzano solo in avanti mantengono il costo a O(n). ✅
Domande Frequenti
La lezione «Finestra variabile con due puntatori» è gratuita?
Sì — il testo completo di «Finestra variabile con due puntatori» è 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 «Finestra variabile con due puntatori»?
Espandere e restringere la finestra fino a soddisfare una condizione 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 2 di 4.
Quanto tempo richiede la lezione «Finestra variabile con due puntatori»?
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
- Somme su finestre di dimensione fissa
- Finestra variabile con due puntatori
- Sottostringa più lunga senza ripetizioni
- Contare le finestre che soddisfano una regola