...
Eroare Algoritmi și structuri de date · Dicționare și set-uri

Two Sum folosește același element de două ori: returnează (0, 0)

Pe scurt

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

Greșit
PYTHON
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]
Corect
PYTHON
vazute = {}
for i, p in enumerate(preturi):
    if buget - p in vazute:
        return vazute[buget - p], i
    vazute[p] = i

Că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

Greșit
PYTHON
if buget - p in poz and buget - p != p:
    return i, poz[buget - p]
Corect
PYTHON
j = poz.get(buget - p)
if j is not None and j != i:
    return i, j

Condiția != p respinge și perechea corectă [3, 3] cu buget 6. Compară indicii, nu valorile.

3Varianta cu două bucle

Greșit
PYTHON
for i in range(n):
    for j in range(n):
        if nums[i] + nums[j] == buget:
            return i, j
Corect
PYTHON
for i in range(n):
    for j in range(i + 1, n):
        if nums[i] + nums[j] == buget:
            return i, j

Bucla interioară trebuie să înceapă de la i + 1, altfel include perechea (i, i).

Repară tu

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).

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
(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.

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.