Sliding window (finestra scorrevole) / Two pointers (due puntatori)
Quando si lavora con gli array, la tecnica della “sliding window” (finestra scorrevole) è molto popolare per risolvere problemi in modo efficiente usando soltanto due puntatori. L’idea principale di questa tecnica è di utilizzare due indici, uno a sinistra e uno a destra, da far scorrere nella giusta direzione ogni volta che si verificano determinate condizioni.
Immaginiamo di voler trovare un certo intervallo “perfetto” (subarray) all’interno di un array. Iniziamo a spostare il puntatore di destra il più possibile, poi regolarizziamo quello di sinistra avvicinandolo a quello di destra. Dopodiché muoviamo di nuovo il puntatore di destra al limite consentito, e poi torniamo a regolare quello di sinistra. Ripetiamo questo procedimento fino a individuare l’intervallo migliore possibile, ed è proprio questa la tecnica nota come “sliding window”.
Sfida - Trovare due numeri che, sommati, diano k
Dato un array ordinato in modo crescente, composto da
n numeri, e un valore obiettivo k, bisogna trovare due numeri nell’array che, sommati, restituiscano k. I valori dell’array sono ordinati in modo crescente e non è consentito utilizzare strutture come dizionari, mappe o hashmap.Input
La prima riga dell’input contiene due interi:
n, il numero di elementi nell’array (1 ≤ n ≤ 10^6), e il numero k (-10^9 < k < 10^9). La riga successiva contiene n interi separati da uno spazio, che rappresentano gli elementi dell’array (-10^9 < a_i < 10^9) in ordine crescente.Output
Il programma deve stampare due interi dell’array la cui somma è
k. Il primo intero stampato deve essere quello più piccolo possibile. Se non è possibile trovare due numeri che soddisfino questa condizione, il programma deve stampare Impossible.Examples
Input | Output |
5 11
-2 3 4 8 9 | 3 8 |
5 1000
-2 3 4 8 9 | Impossible |
Tutorial
Poiché l’array è ordinato in modo crescente, possiamo iniziare con due puntatori: uno sull’inizio dell’array e uno sulla fine, regolando poi la loro posizione in base alla somma dei valori che puntano.
Se la somma dei due puntatori è maggiore di
k, possiamo spostare il puntatore di destra verso sinistra. Se la somma è minore di k, possiamo spostare il puntatore di sinistra verso destra. Infine, se la somma è esattamente k, stampiamo gli elementi corrispondenti e interrompiamo l’esecuzione del programma.n, k = ... # Inizializza n e k
a = ... # Inizializza l'array (in ordine crescente)
l, r = 0, len(a) - 1 # Inizializza i puntatori di sinistra e di destra
while l < r: # Finché l e r non coincidono
if a[l] + a[r] > k: # Se la somma è troppo grande => riducila spostando r
r -= 1
elif a[l] + a[r] < k: # Se la somma è troppo piccola => aumentala spostando l
l += 1
else: # a[l] + a[r] == k => stampa e termina il programma
print(a[l], a[r])
break
else: # while...else = no-break -> non abbiamo trovato nulla
print('Impossible')“Two-pointers” (due puntatori) è un metodo generico che può essere applicato in diversi scenari. L’idea principale è scegliere le posizioni iniziali dei due puntatori (che possono variare molto a seconda del problema) e stabilire la regola per aggiornare tali posizioni (anch’essa può variare da un problema all’altro).
In questo esempio, abbiamo posizionato il puntatore di sinistra all’inizio dell’array e quello di destra alla fine. In altri casi, potremmo aver bisogno di mettere entrambi i puntatori all’inizio. Oppure, in altre circostanze, si potrebbe dover posizionare il puntatore di sinistra alla fine e fare scorrere entrambi verso l’inizio. L’applicazione varia a seconda delle esigenze specifiche.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB