Two Sum folosește același element de două ori: returnează (0, 0)
Ai pus toate valorile în dicționar înainte să cauți perechea, așa că pentru x = buget / 2 găsești chiar elementul curent. Caută complementul înainte să adaugi elementul curent în dicționar (o singură trecere), sau verifică că indicii sunt diferiți.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Problema „două numere cu suma dată” (Two Sum) se rezolvă în O(n) cu un dicționar valoare → index. Varianta greșită construiește întâi dicționarul cu toate valorile, apoi caută buget - x pentru fiecare x. Când x e exact jumătate din buget (3 pentru 6), complementul e chiar x, iar dicționarul îl conține, deci codul returnează perechea (i, i).
Nu primești nicio eroare. Rezultatul e greșit doar pe anumite date, de aceea trece de primele teste.
Varianta corectă face o singură trecere: pentru fiecare element, întâi verifică dacă complementul a fost deja văzut, apoi îl adaugă pe el. Astfel elementul curent nu se poate potrivi cu el însuși, dar două valori egale pe poziții diferite ([3, 3]) sunt găsite.
De ce apare: cauzele frecvente
1Dicționarul conține deja elementul curent
poz = {p: i for i, p in enumerate(preturi)}
for i, p in enumerate(preturi):
if buget - p in poz:
return i, poz[buget - p]vazute = {}
for i, p in enumerate(preturi):
if buget - p in vazute:
return vazute[buget - p], i
vazute[p] = iCăutarea se face doar printre elementele de dinainte, deci i nu se poate potrivi cu el însuși.
2Verificare cu valori în loc de indici
if buget - p in poz and buget - p != p:
return i, poz[buget - p]j = poz.get(buget - p)
if j is not None and j != i:
return i, jCondiția != p respinge și perechea corectă [3, 3] cu buget 6. Compară indicii, nu valorile.
3Varianta cu două bucle
for i in range(n):
for j in range(n):
if nums[i] + nums[j] == buget:
return i, jfor i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == buget:
return i, jBucla interioară trebuie să înceapă de la i + 1, altfel include perechea (i, i).
Repară eroarea, direct în pagină
Funcția doua_produse(preturi, buget) returnează indicii a două produse diferite care costă împreună exact bugetul. Pentru [3, 2, 4] și bugetul 6, testul cu assert pică: produsul 0 e folosit de două ori. Repar-o ca să afișeze (1, 2) și (0, 1).
def doua_produse(preturi, buget):
poz = {p: i for i, p in enumerate(preturi)}
for i, p in enumerate(preturi):
if buget - p in poz:
return i, poz[buget - p]
return None
for preturi, buget, corect in [([3, 2, 4], 6, (1, 2)), ([3, 3], 6, (0, 1))]:
rez = doua_produse(preturi, buget)
assert rez == corect, f'pereche gresita: {rez} in loc de {corect}'
print(rez)(1, 2) (0, 1)
Indiciu
Fă o singură trecere: verifică dacă complementul a fost deja văzut și abia apoi adaugă prețul curent în dicționar.
Reparația
def doua_produse(preturi, buget):
vazute = {}
for i, p in enumerate(preturi):
if buget - p in vazute:
return vazute[buget - p], i
vazute[p] = i
return None
for preturi, buget, corect in [([3, 2, 4], 6, (1, 2)), ([3, 3], 6, (0, 1))]:
rez = doua_produse(preturi, buget)
assert rez == corect, f'pereche gresita: {rez} in loc de {corect}'
print(rez)De ce merge
Dicționarul construit dinainte conținea și prețul 3 de pe poziția 0, deci pentru 3 complementul 3 era găsit chiar la el însuși și funcția returna (0, 0). Acum căutarea se face doar printre prețurile de dinainte: 3 nu găsește nimic, 2 nu găsește 4, iar 4 găsește 2 la indexul 1. Pentru [3, 3], al doilea 3 găsește primul 3, cu index diferit.
Cum o eviți pe viitor
Când cauți perechi, decide explicit dacă un element se poate folosi de două ori și scrie codul astfel încât să compari indici, nu valori. Tiparul „verifică, apoi adaugă” rezolvă problema la majoritatea problemelor cu perechi și sume. Testează mereu cu un element egal cu jumătate din țintă, singur și dublat ([3, 2, 4] și [3, 3] pentru 6).
Întrebări frecvente
De ce varianta cu o trecere găsește [3, 3]?
Primul 3 e adăugat în dicționar. La al doilea 3, complementul 3 e deja acolo, cu alt index, deci perechea (0, 1) e găsită corect.
Ce se întâmplă cu valorile duplicate în dicționar?
Rămâne ultimul index pentru fiecare valoare. Pentru Two Sum e suficient, pentru că returnezi prima pereche găsită.
Erori înrudite
KeyError: 'a' la frecv[litera] += 1 frecv[litera] += 1 citește întâi valoarea cheii, iar la prima apariție a literei cheia nu există încă. Folosește frecv[litera] = frecv.get(litera, 0) + 1, un defaultdict(int) sau direct Counter(text). Time Limit Exceeded: x in lista într-o buclă face soluția O(n²) x in lista caută element cu element (O(n)), iar într-o buclă peste n elemente devine O(n²): pe date mari programul depășește limita de timp. Transformă lista în set o singură dată (set_b = set(b)), apoi x in set_b e O(1) în medie. IndexError: list index out of range la două pointere Pointerul din dreapta a pornit de la len(lista) în loc de len(lista) - 1, sau unul din pointeri a ieșit din listă fără ca bucla să se oprească. Pornește cu dreapta = len(lista) - 1 și pune condiția stanga < dreapta în while. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
