De ce contează?
Ai o trusă de scule plină: chei fixe, chei franceze, șurubelnițe. Un mecanic bun nu se repede cu prima sculă la fiecare șurub — se uită întâi la șurub: ce cap are, cât e de strâns, dacă e ascuns într-un colț. Abia apoi alege scula. Ai învățat deja multe scule pentru vectori — sume parțiale, doi pointeri, căutare binară, vector de frecvență, fereastră glisantă. Lecția asta nu adaugă o sculă nouă: te învață să citești șurubul înainte să întinzi mâna spre trusă.
Ideea-cheie
Aproape orice problemă pe un vector se poate rezolva, teoretic, cu forța brută:
încerci toate perechile, toate subsecvențele, recalculezi totul de la zero la
fiecare întrebare. Funcționează pe exemplul mic din enunț, dar pică la n mare,
fiindcă faci de ordinul a n^2 operații — la n = 100000 asta înseamnă 10
miliarde de pași și depășești limita de timp.
Tehnicile pe care le-ai învățat sunt scurtături: fiecare elimină o muncă repetată anume. Secretul nu e să le memorezi pe toate, ci să recunoști semnalul din enunț care îți spune ce muncă repetată se poate tăia. Enunțul îți strigă tehnica — trebuie doar să-l asculți.
Tehnica nu se alege după cum „arată” vectorul, ci după forma întrebării plus două condiții ascunse pe care le cauți mereu:
- Vectorul e sortat? Sortarea deschide căutarea binară și cei doi pointeri — fără ea, ambele dau răspunsuri greșite.
- Valorile sunt mici? Valori mici (de exemplu până la 1000) deschid vectorul de frecvență, fiindcă încap într-un tablou indexat direct după valoare.
Citește enunțul vânând exact aceste două indicii, nu doar întrebarea în sine.