Il problema Two Sum in Python
In questa lezione risolverai il problema Two Sum, trovando due elementi la cui somma è un valore dato con una sola passata sulla lista.
Introduzione
Il problema
Data una lista di prezzi e un budget, quali due articoli costano esattamente il budget? Controllare ogni coppia funziona ma richiede circa n² / 2 confronti. Se ti ricordi i valori già visti, basta un solo passaggio.
Immaginalo così
Two Sum è come fare la spesa con un budget preciso. Per ogni cartellino calcoli quanto ti manca, poi guardi i tuoi appunti: ho già visto un prodotto che costa esattamente così? Se sì, hai trovato la coppia. Se no, ti segni questo prezzo e dove l'hai visto, e vai avanti.
complement = target - value🤔 Il prezzo che ancora mancaif complement in seen:📋 Quel prezzo è già nei miei appunti?return [seen[complement], index]🛍️ Coppia trovata: le due posizioniseen[value] = index✍️ Segnati questo prezzo e la sua posizione, poi vai avantiIl problema Two Sum chiede le posizioni di due numeri in una lista che sommati danno un valore obiettivo (target). Un dizionario dei valori già visti lo risolve in un solo passaggio, in tempo O(n).
Punti chiave
complement = target - valueè il valore che completerebbe la coppia.seenassocia ogni valore già visto al suo indice, così le ricerche sono veloci.if complement in seen:trova il partner tra i valori precedenti.seen[value] = indexviene salvato dopo il controllo, quindi un valore non viene mai accoppiato con sé stesso.- Per 9, il valore 7 trova il suo partner 2 all'indice 0, e dà
[0, 1].
Quando si usa?
- Trovare coppie con una somma o una differenza data.
- Imparare a usare più memoria per guadagnare velocità con una tabella hash.
- Una domanda da colloquio molto comune e la base di 3-Sum e problemi simili.
Quando non serve
- Input ordinato e poca memoria: due puntatori che partono dalle due estremità non usano memoria extra.
- Ti servono tutte le coppie, non solo una: raccogli i risultati invece di fermarti alla prima coppia trovata.
Codice di esempio
def two_sum(values, target):
seen = {}
for index, value in enumerate(values):
complement = target - value
if complement in seen:
return [seen[complement], index]
seen[value] = index
return []
print(two_sum([2, 7, 11, 15], 9))
Risultato dell'esecuzione
[0, 1]
Spiegazione del codice
Il dizionario seen salva i valori già visitati insieme alle loro posizioni. Per ogni elemento, il programma calcola il complemento complement = target - value e controlla se è già in seen. Dato che la ricerca in un dizionario costa O(1), l'intero algoritmo è O(n) e usa O(n) di memoria aggiuntiva.
Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.
Esercizi di approfondimento
Prova a modificare il codice seguendo i suggerimenti qui sotto. Cambiare il codice e osservare il risultato ti aiuta a capire molto più che leggerlo soltanto.
- Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
- Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
- Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Errori comuni
Salvare prima di controllare
Un valore può accoppiarsi con sé stesso, come 3 + 3 = 6 con un solo 3.
seen[value] = index
if target - value in seen:
if target - value in seen:
return [seen[target - value], index]
seen[value] = index
Hai finito questa lezione?
Segnala come imparata per tenere traccia dei tuoi progressi.
Esercitati con una sfida
Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.
Tutte le sfide