De ce contează?
Cauți două cărți pe un raft ordonat după grosime care, puse împreună, să aibă exact o anumită înălțime. Pui un deget la cea mai subțire și unul la cea mai groasă. Dacă suma e prea mare, muți degetul de sus spre cărți mai subțiri; dacă e prea mică, pe cel de jos spre mai groase. Te apropii din ambele capete.
Ideea: doi indici care se mișcă inteligent
Two pointers folosește doi indici care parcurg vectorul mișcându-se după o condiție, în loc să verifici toate perechile. Pe multe probleme transformă O(n²) în O(n). Funcționează des pe vectori sortați, unde mișcarea unui indice are efect previzibil asupra rezultatului.
Exemplu clasic: pereche cu sumă dată
Vector sortat {1, 3, 4, 6, 8, 11}, caut o pereche cu suma 10. st la început, dr la final:
| st | dr | v[st]+v[dr] | comparație | mișcare |
|---|---|---|---|---|
| 0 | 5 | 1+11=12 | > 10 | dr-- |
| 0 | 4 | 1+8=9 | < 10 | st++ |
| 1 | 4 | 3+8=11 | > 10 | dr-- |
| 1 | 3 | 3+6=9 | < 10 | st++ |
| 2 | 3 | 4+6=10 | = 10 | găsit! |
| v | 1 | 3 | 4 | 6 | 8 | 11 |
0 | 1 | 2 | 3 | 4 | 5 | |
st | dr |
Implementare C++
#include <iostream>
using namespace std;
int main() {
int v[] = {1, 3, 4, 6, 8, 11}, n = 6, tinta = 10;
int st = 0, dr = n - 1;
bool gasit = false;
while (st < dr) {
int suma = v[st] + v[dr];
if (suma == tinta) { gasit = true; break; }
else if (suma < tinta) st++; // suma prea mica -> crestem st
else dr--; // suma prea mare -> scadem dr
}
if (gasit) cout << v[st] << " + " << v[dr] << " = " << tinta << "\n";
else cout << "nu exista pereche\n";
return 0;
}De ce funcționează: pe vector sortat, dacă suma e prea mică, singurul mod de a o mări e
să crești st (spre valori mai mari). Dacă e prea mare, scazi dr. Niciun indice nu se
întoarce, deci faci cel mult n pași.
Alte tipare two pointers
- Eliminarea duplicatelor dintr-un vector sortat (un indice scrie, altul citește).
- Interclasarea a doi vectori sortați (un indice per vector — vezi lecția dedicată).
- Fereastra glisantă de lungime variabilă (capetele se mișcă independent).
Complexitate
| Metodă | Timp | Spațiu |
|---|---|---|
| two pointers | O(n) | O(1) |
| toate perechile | O(n²) | O(1) |
Pe vector nesortat, adaugă sortarea: O(n log n) o dată, apoi O(n).
Capcane reale la two pointers:
- Vector nesortat: pentru pereche cu sumă, logica mișcării presupune sortare. Pe date nesortate dă rezultate greșite.
- Condiția
st < dr: cust <= drai compara un element cu el însuși; cu mișcare greșită poți sări soluția. - Miști ambii indici deodată fără motiv: la majoritatea problemelor, doar unul se mișcă per pas, în funcție de comparație.
- Buclă infinită: dacă pe vreo ramură niciun indice nu se mișcă, bucla nu se termină.
Vizualizare
Urmărește cum cei doi indici converg din capete în funcție de comparația cu ținta:
Observă că la fiecare pas se mișcă un singur indice — cel care apropie suma de țintă.
Spațiul dintre st și dr se micșorează mereu, garantând oprirea.
De reținut
- Two pointers = doi indici care se mișcă după o condiție, des pe vector sortat.
- Suma prea mică →
st++; prea mare →dr--; converg în O(n), nu O(n²). - Indicii nu se întorc niciodată → cel mult n pași; pe date nesortate, sortează întâi.