Fereastra glisantă variabilă se micșorează cu if în loc de while: rezultatul iese prea mare
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
suma += nums[dr]
if suma >= tinta:
best = min(best, dr - st + 1)
suma -= nums[st]
st += 1suma += nums[dr]
while suma >= tinta:
best = min(best, dr - st + 1)
suma -= nums[st]
st += 1Cu 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
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)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ă 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).
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)1 2
Indiciu
Fereastra trebuie micșorată de câte ori e nevoie, nu o singură dată.
Reparația
def cea_mai_scurta(nums, tinta):
st = 0
suma = 0
best = float('inf')
for dr in range(len(nums)):
suma += nums[dr]
while 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)De ce merge
Când apare 10, suma ferestrei devine 14, iar fereastra [1, 1, 1, 1, 10] e validă. Cu if, programul nota lungimea 5, scotea un singur 1 și trecea mai departe, fără să mai încerce ferestrele mai scurte. Cu while, fereastra se strânge pas cu pas: 4, 3, 2 și în final 1, cât timp suma rămâne cel puțin 10, și găsește lungimea minimă 1. Fiecare element intră și iese o singură dată, deci complexitatea rămâne O(n).
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
Fereastra glisantă sare peste ultima fereastră (off-by-one la range) O listă cu n elemente are n - k + 1 ferestre de lungime k, deci bucla trebuie să fie range(len(lista) - k + 1). Cu range(len(lista) - k) ultima fereastră nu e verificată, iar rezultatul e greșit fără nicio eroare. Suma pe interval cu sume prefix iese greșită (prefix[j] - prefix[i] fără +1) Cu prefix[k] = suma primelor k elemente, suma de la i la j inclusiv este prefix[j + 1] - prefix[i]. Dacă scrii prefix[j] - prefix[i], pierzi elementul j; dacă scrii prefix[j] - prefix[i - 1] cu altă convenție, pici la i = 0. Kadane returnează 0 pentru o listă doar cu numere negative Ai pornit maximul (sau suma curentă) de la 0, iar când toate numerele sunt negative, nicio secvență nu trece de 0. Pornește de la primul element: cel_mai_bun = curent = nums[0], apoi curent = max(x, curent + x) pentru restul. Î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.
