Algoritmi → Napredne tehnike → Tehnika dva pokazivača

Tehnika dva pokazivača

Pokazivači sa dva kraja: par sa zadatim zbirom

Zadatak: u sortiranom nizu pronaći dva elementa čiji je zbir tačno S.

Postavimo i na početak, a j na kraj niza. Ako je a[i] + a[j] premalo, jedini način da zbir poraste je da pomerimo i udesno. Ako je preveliko, pomeramo j ulevo. Pokazivači se kreću jedan ka drugom, pa ukupno ima najviše n koraka.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    long long S;
    cin >> n >> S;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;         // niz je sortiran rastuće

    int i = 0, j = n - 1;
    while (i < j) {
        long long zbir = a[i] + a[j];
        if (zbir == S) {
            cout << a[i] << " " << a[j] << endl;
            return 0;
        }
        if (zbir < S) i++;              // treba veći zbir
        else j--;                       // treba manji zbir
    }
    cout << "NEMA" << endl;
    return 0;
}

Pokletni prozor: najduži deo sa zbirom najviše S

Zadatak: dat je niz nenegativnih brojeva. Naći najduži uzastopni deo čiji zbir nije veći od S.

Održavamo „prozor“ a[l..r] i njegov zbir. Pomeramo desni kraj r i dodajemo element; dok je zbir prevelik, izbacujemo element sa levog kraja (l++). Pošto su brojevi nenegativni, skraćivanje sleva uvek smanjuje zbir. Svaki element jednom uđe i najviše jednom izađe iz prozora – ukupno O(n).

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    long long S;
    cin >> n >> S;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;

    long long zbir = 0;
    int l = 0, najduzi = 0;
    for (int r = 0; r < n; r++) {
        zbir += a[r];                   // a[r] ulazi u prozor
        while (zbir > S) {              // prevelik zbir: skrati sleva
            zbir -= a[l];
            l++;
        }
        najduzi = max(najduzi, r - l + 1);
    }
    cout << najduzi << endl;
    return 0;
}

Dva niza istovremeno

Spajanje dva sortirana niza u sortiranju objedinjavanjem je takođe tehnika dva pokazivača: po jedan indeks u svakom nizu. Na isti način se u O(n + m) nalaze zajednički elementi dva sortirana niza:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    cin >> m;
    vector<int> b(m);
    for (int &x : b) cin >> x;

    int i = 0, j = 0;
    while (i < n && j < m) {
        if (a[i] < b[j]) i++;
        else if (b[j] < a[i]) j++;
        else {                          // zajednički element
            cout << a[i] << " ";
            i++;
            j++;
        }
    }
    cout << endl;
    return 0;
}

Kada radi?

Tehnika radi kada postoji monotonost: pomeranje pokazivača u jednom smeru sigurno ne može da propusti rešenje. Kod para sa zbirom to garantuje sortiranost, a kod prozora to što su brojevi nenegativni. Ako u nizu ima negativnih brojeva, prozor ne radi – tada pomažu prefiksne sume.

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje