Algoritmo Two Sum in Python
Una hash map evita due cicli annidati.
Che cos’è Algoritmo Two Sum?
Una hash map evita due cicli annidati.
Trova due valori la cui somma è il target.
Quando si usa?
- Comprendere algoritmi e strutture dati.
- Osservare ogni passaggio e gestire i casi limite.
- Confrontare tempo di esecuzione e memoria.
Codice di esempio
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))Output previsto
[0, 1]Come funziona
Il complemento si cerca in O(1): tempo totale O(n), memoria O(n).
Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.
Esercizi pratici
Modifica gli input e verifica i casi limite prima di usare dataset più grandi.
- Prova input vuoto, un elemento e duplicati.
- Stampa lo stato dopo ogni passaggio.
- Confronta le prestazioni con un’altra soluzione.