Tehnica Two Pointers în C++

Ce este Two Pointers?

O tehnică de optimizare care folosește doi indici (pointeri) pentru a parcurge eficient un vector, reducând complexitatea de la O(n²) la O(n).

Problema 1: Sumă cu Target în Vector Sortat

Copiază
1#include <iostream>
2#include <vector>
3using namespace std;
4
5pair<int, int> gasesteSuma(vector<int>& v, int target) {
6    int st = 0, dr = v.size() - 1;
7    
8    while (st < dr) {
9        int suma = v[st] + v[dr];
10        
11        if (suma == target)
12            return {st, dr};
13        else if (suma < target)
14            st++;
15        else
16            dr--;
17    }
18    
19    return {-1, -1}; // Nu există
20}
21
22int main() {
23    vector<int> v = {1, 2, 4, 6, 8, 9, 14, 15};
24    int target = 13;
25    
26    auto [i, j] = gasesteSuma(v, target);
27    if (i != -1)
28        cout << v[i] << " + " << v[j] << " = " << target << endl;
29    
30    return 0;
31}

Problema 2: Eliminare Duplicate (In-Place)

Copiază
1int eliminaDuplicate(vector<int>& v) {
2    if (v.empty()) return 0;
3    
4    int pozUnica = 0;
5    
6    for (int i = 1; i < v.size(); i++) {
7        if (v[i] != v[pozUnica]) {
8            pozUnica++;
9            v[pozUnica] = v[i];
10        }
11    }
12    
13    return pozUnica + 1; // Lungimea vectorului unic
14}

Problema 3: Container cu Apă Maximă

Copiază
1int maxApa(vector<int>& inaltime) {
2    int st = 0, dr = inaltime.size() - 1;
3    int maxAria = 0;
4    
5    while (st < dr) {
6        int h = min(inaltime[st], inaltime[dr]);
7        int latime = dr - st;
8        maxAria = max(maxAria, h * latime);
9        
10        if (inaltime[st] < inaltime[dr])
11            st++;
12        else
13            dr--;
14    }
15    
16    return maxAria;
17}

Problema 4: Verificare Palindrom

Copiază
1bool estePalindrom(const string& s) {
2    int st = 0, dr = s.length() - 1;
3    
4    while (st < dr) {
5        // Sărim peste caractere non-alfanumerice
6        while (st < dr && !isalnum(s[st])) st++;
7        while (st < dr && !isalnum(s[dr])) dr--;
8        
9        if (tolower(s[st]) != tolower(s[dr]))
10            return false;
11        
12        st++;
13        dr--;
14    }
15    
16    return true;
17}

Problema 5: Three Sum

Copiază
1vector<vector<int>> threeSum(vector<int>& v, int target) {
2    vector<vector<int>> rezultat;
3    sort(v.begin(), v.end());
4    
5    for (int i = 0; i < v.size() - 2; i++) {
6        if (i > 0 && v[i] == v[i-1]) continue; // Evită duplicate
7        
8        int st = i + 1, dr = v.size() - 1;
9        
10        while (st < dr) {
11            int suma = v[i] + v[st] + v[dr];
12            
13            if (suma == target) {
14                rezultat.push_back({v[i], v[st], v[dr]});
15                while (st < dr && v[st] == v[st+1]) st++;
16                while (st < dr && v[dr] == v[dr-1]) dr--;
17                st++; dr--;
18            }
19            else if (suma < target) st++;
20            else dr--;
21        }
22    }
23    
24    return rezultat;
25}