Algoritmi Python

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.

  • Intermedio
  • 2 min di lettura
  • 1 esempio eseguibile

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.

Dalla spesa con il budget al codice
complement = target - value🤔 Il prezzo che ancora manca
if complement in seen:📋 Quel prezzo è già nei miei appunti?
return [seen[complement], index]🛍️ Coppia trovata: le due posizioni
seen[value] = index✍️ Segnati questo prezzo e la sua posizione, poi vai avanti
Cerca il prezzo che manca invece di controllare tutte le coppie.
In una frase

Il 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

  1. complement = target - value è il valore che completerebbe la coppia.
  2. seen associa ogni valore già visto al suo indice, così le ricerche sono veloci.
  3. if complement in seen: trova il partner tra i valori precedenti.
  4. seen[value] = index viene salvato dopo il controllo, quindi un valore non viene mai accoppiato con sé stesso.
  5. 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

Esegui codice →
main.py
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))
Crea un pulsante Run per questo esempio

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.

  1. Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
  2. Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
  3. Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Esegui nel compilatore Python →

Errori comuni

Salvare prima di controllare

Un valore può accoppiarsi con sé stesso, come 3 + 3 = 6 con un solo 3.

Problema
seen[value] = index
if target - value in seen:
Correzione
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