Tehnica Two Pointers (doi indici)

Two Pointers este o tehnică în care folosim doi indici care se deplasează prin vector, de obicei în aceeași direcție sau din direcții opuse. În loc să verificăm toate perechile posibile (O(n^2)), găsim răspunsul în O(n).

Când folosim Two Pointers?

• Când vectorul este sortat
• Când căutăm perechi cu o proprietate (sumă, diferență)
• Când vrem să eliminăm duplicate
• Când procesăm două secvențe simultan

Varianta 1: doi indici din direcții opuse

Problema: pereche cu suma S

Avem un vector sortat și un număr S. Găsim două elemente a căror sumă este S.

Ideea

• Punem un indice st la început și un indice dr la sfârșit.
• Calculăm v[st] + v[dr].
• Dacă suma este prea mică, mutăm st la dreapta (creștem suma).
• Dacă suma este prea mare, mutăm dr la stânga (micșorăm suma).
• Dacă suma este exact S, am găsit!

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[100001];
int n, s;

int main()
{
    fin >> n >> s;
    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    int st = 1, dr = n;
    int gasit = 0;

    while (st < dr) {
        int suma = v[st] + v[dr];

        if (suma == s) {
            fout << v[st] << " + " << v[dr] << " = " << s;
            gasit = 1;
            break;
        } else if (suma < s) {
            st++;
        } else {
            dr--;
        }
    }

    if (gasit == 0) {
        fout << "NU";
    }

    return 0;
}

date.in:

7 12
1 3 4 5 7 9 11

date.out:

3 + 9 = 12

Pas cu pas

De fapt, în acest caz găsim imediat. Alt exemplu cu S = 10:

De ce funcționează?

Vectorul este sortat. Dacă suma e prea mică, singurul mod de a o crește este să mărim elementul mic (st++). Dacă e prea mare, singurul mod de a o micșora este să micșorăm elementul mare (dr–).

Varianta 2: doi indici în aceeași direcție

Problema: cel mai lung subșir fără duplicate

Avem un vector și vrem să găsim cea mai lungă secvență de elemente consecutive în care nu există duplicate.

Ideea

Folosim doi indici st și dr care definesc o fereastră. Extindem dr la dreapta cât timp nu avem duplicate. Când apare un duplicat, mutăm st la dreapta până îl eliminăm.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[100001];
int fr[100001]; // frecventa valorilor in fereastra curenta
int n;

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    int st = 1;
    int maxLung = 0;

    for (int dr = 1; dr <= n; dr++) {
        fr[v[dr]]++;

        while (fr[v[dr]] > 1) {
            fr[v[st]]--;
            st++;
        }

        int lung = dr - st + 1;
        if (lung > maxLung) {
            maxLung = lung;
        }
    }

    fout << maxLung;

    return 0;
}

date.in:

9
1 3 2 3 4 5 2 6 7

date.out:

5

Secvența 3 4 5 2 6 (pozițiile 4-8) are lungimea 5, fără duplicate.

Pas cu pas (simplificat)

Răspuns: 6 (secvența 3,4,5,2,6,7).

Problema: numărul de perechi cu diferența D

Vector sortat. Câte perechi (v[i], v[j]) cu i < j au v[j] - v[i] = D?

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[100001];
int n, d;

int main()
{
    fin >> n >> d;
    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    int st = 1;
    int cnt = 0;

    for (int dr = 2; dr <= n; dr++) {
        while (v[dr] - v[st] > d && st < dr) {
            st++;
        }
        if (v[dr] - v[st] == d) {
            cnt++;
        }
    }

    fout << cnt;

    return 0;
}

date.in:

7 3
1 2 3 4 5 6 7

date.out:

4

Perechile: (1,4), (2,5), (3,6), (4,7).

Problema: reuniunea a două mulțimi sortate

Am văzut deja la interclasare - doi indici care avansează pe doi vectori. Aceasta este tot o variantă de Two Pointers.

int i = 1, j = 1;

while (i <= n && j <= m) {
    if (a[i] < b[j]) {
        fout << a[i] << " ";
        i++;
    } else if (a[i] > b[j]) {
        fout << b[j] << " ";
        j++;
    } else {
        fout << a[i] << " "; // egal - afișăm o dată
        i++;
        j++;
    }
}

Schema generală Two Pointers

Direcții opuse (vector sortat):

st -->            <-- dr
[  ...  ...  ...  ...  ]

Condiția: while (st < dr)

Aceeași direcție (fereastră):

st -->   dr -->
[  ...  ...  ...  ...  ]

Condiția: for dr de la 1 la n, st avansează când e necesar

Greșeli frecvente

1. Vectorul nu este sortat (când trebuie)

Varianta cu direcții opuse funcționează doar pe vectori sortați. Fără sortare, logica “crește st / scade dr” nu are sens.

2. Condiția st < dr vs st <= dr

• La perechi: st < dr (nu vrem aceeași poziție)
• La căutare binară: st <= dr (verificăm și elementul unic)

3. Indici care nu avansează

Dacă nu mutăm niciodată st sau dr, bucla devine infinită. La fiecare pas, cel puțin un indice trebuie să avanseze.

Ce să reții

• Two Pointers folosește doi indici care se deplasează inteligent prin vector.
• Direcții opuse (pe vector sortat): perechi cu suma/diferența dată.
• Aceeași direcție (fereastră): secvențe fără duplicate, secvențe cu proprietăți.
• Complexitate: O(n) în loc de O(n^2).
• Vectorul trebuie sortat pentru varianta cu direcții opuse.
• Este una dintre cele mai frecvente tehnici la concursuri.

Probleme

pbinfoSecvkdistincte→

pbinfoSumainsecv→

pbinfoRgb→

pbinfoPalindrom4→