Doi pointeri: pereche cu sumă dată în C++

Într-un vector sortat crescător, poți găsi două elemente cu sumă dată fără să încerci toate perechile. Pornești de la cele două capete și elimini la fiecare pas o poziție care nu mai poate participa la soluție.

Cerință și precondiție

Citim 2 ≤ n ≤ 1000, suma țintă și n numere întregi în ordine nedescrescătoare. Valorile au modulul cel mult 10^9, iar ținta are modulul cel mult 2·10^9. Afișăm pozițiile de la 1 ale unei perechi valide, sau NU EXISTA. Cele două poziții trebuie să fie diferite, dar valorile pot coincide. Nu cerem toate perechile și nici o departajare lexicografică.

Pentru 1,2,4,6,8 și ținta 10, perechea de capete 1+8 este prea mică; 2+8 este soluție.Mărește schema ↗

De ce mutăm un singur capăt

Dacă a[st] + a[dr] este prea mică, orice pereche formată din a[st] și un element aflat înainte de dr are suma cel mult egală cu cea curentă. Putem elimina poziția st. Dacă suma este prea mare, orice pereche formată din a[dr] și un element aflat după st are suma cel puțin egală cu cea curentă. Eliminăm poziția dr.

Pentru 1 2 4 6 8 și ținta 10, prima sumă este 1+8=9. Mutăm st spre dreapta și găsim 2+8=10, deci pozițiile 2 și 5. Fiecare mutare se justifică prin ordonarea datelor.

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int main() {
    int n; long long tinta; cin >> n >> tinta;
    long long a[1000];
    for (int i = 0; i < n; ++i) cin >> a[i];
    int st = 0, dr = n - 1;
    while (st < dr) {
        long long suma = a[st] + a[dr];
        if (suma == tinta) { cout << st+1 << ' ' << dr+1 << '\n'; return 0; }
        if (suma < tinta) ++st;
        else --dr;
    }
    cout << "NU EXISTA\n";
}

Varianta echivalentă cu std::vector

Indicii și datele de intrare rămân aceleași. Containerul este construit cu numărul de elemente folosite; accesul prin [] cere în continuare indici valizi.

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n; long long tinta; cin >> n >> tinta;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    int st = 0, dr = n - 1;
    while (st < dr) {
        long long suma = a[st] + a[dr];
        if (suma == tinta) { cout << st+1 << ' ' << dr+1 << '\n'; return 0; }
        if (suma < tinta) ++st;
        else --dr;
    }
    cout << "NU EXISTA\n";
}

Limite și capcane

În varianta clasică, capacitatea este 1000, iar dimensiunea logică este n. Ambii indici rămân în intervalul 0..n-1. Condiția st < dr împiedică folosirea aceluiași element de două ori. Pentru vectorul 5 5 și ținta 10, răspunsul este valid: pozițiile sunt diferite.

Pe un vector nesortat, argumentul de eliminare nu mai este adevărat. Dacă sortezi, pierzi pozițiile originale, dacă nu le păstrezi separat. Alege această metodă când datele sunt deja sortate sau când cerința permite acea transformare. Numerele negative nu o invalidează; ordonarea este proprietatea necesară.

Avem cel mult n-1 mutări ale capetelor, deci O(n) timp. Starea suplimentară este O(1), pe lângă vector. Suma este calculată în long long, deoarece elementele sunt deja de acest tip.

Exersează

Verifică -5 -1 3 9 cu ținta 4: prima pereche găsită este pe pozițiile 1 și 4. Pentru 1 2 3 și ținta 8 nu există soluție. Pentru 1 3 5 și ținta 6, pozițiile 1 și 3 formează soluția; poziția 2 nu poate fi utilizată de două ori.

Dacă trebuie să numeri toate perechile, nu te opri la prima și tratează multiplicitatea valorilor egale. Acesta este un alt contract, cu alte actualizări.

Compară cu căutarea în vectori, sortarea și estimarea complexității.

Întrebări frecvente

De ce funcționează doi pointeri pentru o sumă într-un vector sortat?

Ordinea permite eliminarea sigură a unui capăt. Dacă suma este prea mică, crești indicele stâng; dacă este prea mare, micșorezi indicele drept. Fiecare pas elimină candidați care nu pot produce ținta cu acel capăt.

Pot folosi aceeași poziție de două ori pentru suma cerută?

Nu în această problemă. Condiția stanga < dreapta păstrează două poziții distincte. Valorile pot fi egale: două apariții ale lui 5 pot forma suma 10.

Funcționează metoda celor doi pointeri pe un vector nesortat?

Nu direct, deoarece decizia de eliminare a unui capăt nu mai este justificată. Poți sorta dacă cerința permite; dacă se cer pozițiile originale, trebuie păstrată și legătura cu ele.