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

Fereastra glisantă sare peste ultima fereastră (off-by-one la range)

Pe scurt

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.

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

Ce înseamnă

La sliding window muți o fereastră de lungime k peste listă și calculezi ceva pentru fiecare poziție (suma, media, maximul). Ferestrele încep la indicii 0, 1, ..., n - k, adică sunt n - k + 1 ferestre. Bucla corectă este for i in range(len(lista) - k + 1).

Cu range(len(lista) - k) bucla se oprește cu o poziție mai devreme. Python nu dă nicio eroare, pentru că toți indicii folosiți sunt valizi; doar că ultima fereastră lipsește. Dacă răspunsul corect era chiar în ultima fereastră, funcția returnează un rezultat greșit, iar când n == k nu verifică nicio fereastră.

Acesta este un bug off-by-one. În „Repară tu” testele folosesc assert, deci vezi AssertionError cu valoarea primită. În propriul cod, testează mereu cazul în care răspunsul e la final și cazul len(lista) == k.

De ce apare: cauzele frecvente

1Numărul de ferestre calculat greșit

Greșit
PYTHON
def suma_maxima(v, k):
    best = 0
    for i in range(len(v) - k):
        best = max(best, sum(v[i:i + k]))
    return best
Corect
PYTHON
def suma_maxima(v, k):
    best = sum(v[:k])
    for i in range(1, len(v) - k + 1):
        best = max(best, sum(v[i:i + k]))
    return best

Ultima fereastră începe la len(v) - k, iar range exclude capătul, deci limita trebuie să fie len(v) - k + 1.

2Pornești maximul de la 0

Greșit
PYTHON
best = 0
for i in range(len(v) - k + 1):
    best = max(best, sum(v[i:i + k]))
Corect
PYTHON
best = sum(v[:k])
for i in range(1, len(v) - k + 1):
    best = max(best, sum(v[i:i + k]))

Dacă toate valorile sunt negative, maximul real e sub 0, iar inițializarea cu 0 dă un rezultat care nu există. Pornește cu prima fereastră.

3Fereastra glisantă incrementală

Greșit
PYTHON
s = sum(v[:k])
for i in range(k, len(v) - 1):
    s += v[i] - v[i - k]
Corect
PYTHON
s = sum(v[:k])
for i in range(k, len(v)):
    s += v[i] - v[i - k]

În varianta O(n), i este elementul care intră în fereastră și trebuie să meargă până la ultimul indice, len(v) - 1 inclusiv.

Repară tu

Repară eroarea, direct în pagină

Funcția cele_mai_bune_zile(vizite, k) returnează suma maximă a vizitelor din k zile consecutive. Testele cu assert pică: când cele mai bune zile sunt la final, rezultatul e greșit. Repar-o ca testele să treacă și să afișeze 25, 9 și -3.

Codul care dă eroarea
PYTHON
def cele_mai_bune_zile(vizite, k):
    best = 0
    for i in range(len(vizite) - k):
        best = max(best, sum(vizite[i:i + k]))
    return best

r1 = cele_mai_bune_zile([3, 1, 4, 10, 15], 2)
r2 = cele_mai_bune_zile([4, 5], 2)
r3 = cele_mai_bune_zile([-5, -3, -8], 1)
assert (r1, r2, r3) == (25, 9, -3), f"fereastra gresita: {r1}, {r2}, {r3}"
print(r1)
print(r2)
print(r3)
După reparație, programul afișează
25
9
-3
Indiciu

Numără câte ferestre de lungime k are o listă cu n elemente și pornește maximul de la prima fereastră, nu de la 0.

Cum o eviți pe viitor

Înainte de buclă, scrie în comentariu câte ferestre există (n - k + 1) și care e ultimul indice de start (n - k). Verifică formula pe un exemplu mic: pentru n = 5, k = 2 ai ferestrele 0-1, 1-2, 2-3, 3-4, deci 4. Testează funcția pe trei cazuri: răspunsul la început, răspunsul la final și len(lista) == k.

Întrebări frecvente

De ce nu primesc nicio eroare?

Pentru că bucla folosește doar indici valizi: se oprește prea devreme, nu prea târziu. Erorile off-by-one de acest tip dau rezultate greșite, nu excepții, și se prind doar cu teste.

Cum îmi dau seama dacă formula e n - k sau n - k + 1?

Ia cel mai mic caz: n = k. Există exact o fereastră, deci bucla trebuie să ruleze o dată: range(n - k + 1) = range(1). range(n - k) = range(0) nu rulează deloc.

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.