...
Eroare Algoritmi și structuri de date · Tablouri, două pointere și ferestre

Fereastra glisantă variabilă se micșorează cu if în loc de while: rezultatul iese prea mare

Pe scurt

La fereastra de lungime variabilă, marginea din stânga trebuie mutată cât timp condiția e încă îndeplinită, nu o singură dată. Înlocuiește if suma >= tinta cu while suma >= tinta, ca fereastra să se strângă până la cea mai mică lungime validă.

Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la

Ce înseamnă

Tehnica ferestrei glisante variabile are doi indici: dr extinde fereastra cu câte un element, iar st o micșorează. La problemele de tipul „cea mai scurtă secvență cu suma cel puțin K” sau „cel mai lung fragment cu cel mult k litere distincte”, după fiecare extindere trebuie să muți st de câte ori e nevoie, nu doar o dată.

Cu if, fereastra pierde cel mult un element la fiecare pas. Dacă un element nou mare face ca mai multe elemente din stânga să devină inutile, ele rămân în fereastră, iar lungimea minimă găsită e prea mare. Nu apare nicio eroare: rezultatul e doar greșit, de obicei pe cazurile cu un element mare la final.

Regula: condiția de micșorare se pune într-un while, iar actualizarea răspunsului se face în interiorul lui (pentru minim) sau după el (pentru maxim).

De ce apare: cauzele frecvente

1Cea mai scurtă secvență cu suma cel puțin K

Greșit
PYTHON
suma += nums[dr]
if suma >= tinta:
    best = min(best, dr - st + 1)
    suma -= nums[st]
    st += 1
Corect
PYTHON
suma += nums[dr]
while suma >= tinta:
    best = min(best, dr - st + 1)
    suma -= nums[st]
    st += 1

Cu while, fereastra se strânge cât timp suma rămâne suficientă, deci la fiecare dr găsești cea mai scurtă fereastră care se termină acolo.

2Cel mult k elemente distincte

Greșit
PYTHON
if len(frecv) > k:
    frecv[s[st]] -= 1
    if frecv[s[st]] == 0:
        del frecv[s[st]]
    st += 1
best = max(best, dr - st + 1)
Corect
PYTHON
while len(frecv) > k:
    frecv[s[st]] -= 1
    if frecv[s[st]] == 0:
        del frecv[s[st]]
    st += 1
best = max(best, dr - st + 1)

Dacă scoți o singură literă, fereastra poate rămâne cu mai mult de k litere distincte, iar best numără o fereastră invalidă.

Repară tu

Repară eroarea, direct în pagină

Funcția cea_mai_scurta(nums, tinta) caută lungimea celei mai scurte secvențe consecutive cu suma cel puțin tinta. Testul cu assert pică: pentru [1, 1, 1, 1, 10] și ținta 10 returnează 5. Repar-o ca să afișeze 1 și 2 (pentru [2, 3, 1, 2, 4, 3] cu ținta 7).

Codul care dă eroarea
PYTHON
def cea_mai_scurta(nums, tinta):
    st = 0
    suma = 0
    best = float('inf')
    for dr in range(len(nums)):
        suma += nums[dr]
        if suma >= tinta:
            best = min(best, dr - st + 1)
            suma -= nums[st]
            st += 1
    return best if best != float('inf') else 0

r1 = cea_mai_scurta([1, 1, 1, 1, 10], 10)
r2 = cea_mai_scurta([2, 3, 1, 2, 4, 3], 7)
assert (r1, r2) == (1, 2), f'fereastra prea lunga: {r1}, {r2}'
print(r1)
print(r2)
După reparație, programul afișează
1
2
Indiciu

Fereastra trebuie micșorată de câte ori e nevoie, nu o singură dată.

Cum o eviți pe viitor

Scrie invariantul ferestrei într-un comentariu („suma din fereastră e sub țintă”, „cel mult k distincte”) și refă-l după fiecare pas cu un while. Testează mereu un caz în care ultimul element e foarte mare, de exemplu [1, 1, 1, 1, 10] cu ținta 10: răspunsul corect e 1. Dacă primești lungimea întregii liste, micșorarea se face prea puțin.

Întrebări frecvente

Nu e while în for O(n²)?

Nu. Indicele st doar crește și nu depășește niciodată n, deci în total bucla interioară face cel mult n pași pe toată execuția. Algoritmul rămâne O(n).

Am văzut soluții corecte cu if. Cum așa?

Există un truc pentru „cea mai lungă fereastră”: fereastra nu se micșorează niciodată, doar alunecă, iar răspunsul e lungimea ei finală. Merge doar la maxim și doar dacă răspunsul e calculat diferit. La minim, ai nevoie de while.

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.