Aplicaciones Prácticas

Patrones que aparecen en competencias

Los mapas y sets son herramientas versátiles. Aquí veremos los patrones más comunes.

Patrón 1: Two Sum (suma de dos)

Problema: Dado un arreglo de N números, ¿existen dos que sumen exactamente K?

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

int main() {
    int n, k;
    cin >> n >> k;

    set<int> vistos;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        int complemento = k - x;
        if (vistos.count(complemento)) {
            cout << "Sí: " << x << " + " << complemento << " = " << k << endl;
            return 0;
        }
        vistos.insert(x);
    }

    cout << "No existen dos números que sumen " << k << endl;
    return 0;
}

Idea: Para cada número x, preguntamos: "¿ya vi un número que sea k - x?" Si sí, encontramos la pareja. Complejidad: $O(n \log n)$ con set, $O(n)$ con unordered_set.

Patrón 2: Primer elemento no repetido

Problema: Dada una cadena, encuentra la primera letra que no se repite.

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

int main() {
    string s;
    cin >> s;

    map<char, int> freq;
    for (char c : s) freq[c]++;

    for (char c : s) {
        if (freq[c] == 1) {
            cout << c << endl;
            return 0;
        }
    }

    cout << "Todos se repiten" << endl;
    return 0;
}

Patrón 3: Subarreglo con suma K

Problema: ¿Cuántos subarreglos contiguos suman exactamente K?

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

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> v(n);
    for (int &x : v) cin >> x;

    map<long long, int> prefijos;
    prefijos[0] = 1;  // Suma prefija vacía
    long long suma = 0;
    int respuesta = 0;

    for (int i = 0; i < n; i++) {
        suma += v[i];
        // ¿Existe un prefijo anterior tal que suma - prefijo = k?
        if (prefijos.count(suma - k)) {
            respuesta += prefijos[suma - k];
        }
        prefijos[suma]++;
    }

    cout << respuesta << endl;
    return 0;
}

Idea: Si la suma prefija actual es S y existe una suma prefija anterior S - K, entonces hay un subarreglo que suma K. Guardamos las sumas prefijas en un mapa para buscarlas en $O(\log n)$.

Patrón 4: Elementos distintos en ventana deslizante

Problema: Dado un arreglo de N números y un tamaño de ventana W, para cada ventana de tamaño W, ¿cuántos elementos distintos hay?

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

int main() {
    int n, w;
    cin >> n >> w;

    vector<int> v(n);
    for (int &x : v) cin >> x;

    map<int, int> ventana;  // valor -> frecuencia en la ventana

    // Llenar la primera ventana
    for (int i = 0; i < w; i++) {
        ventana[v[i]]++;
    }
    cout << ventana.size() << " ";

    // Deslizar la ventana
    for (int i = w; i < n; i++) {
        // Agregar el nuevo elemento
        ventana[v[i]]++;

        // Quitar el elemento que sale
        ventana[v[i - w]]--;
        if (ventana[v[i - w]] == 0) {
            ventana.erase(v[i - w]);  // Eliminar si la frecuencia llega a 0
        }

        cout << ventana.size() << " ";
    }
    cout << endl;

    return 0;
}

Patrón 5: Anagramas

Problema: Verifica si dos cadenas son anagramas (mismas letras, diferente orden).

bool sonAnagramas(string a, string b) {
    if (a.size() != b.size()) return false;

    map<char, int> freq;
    for (char c : a) freq[c]++;
    for (char c : b) freq[c]--;

    for (auto &[c, f] : freq) {
        if (f != 0) return false;
    }
    return true;
}

Patrón 6: Coordenadas comprimidas

Cuando los valores son muy grandes pero pocos, los "comprimimos" a un rango pequeño:

vector<int> v = {1000000000, 3, 500, 3, 1000000000};

// Paso 1: extraer valores únicos y ordenarlos
set<int> unicos(v.begin(), v.end());

// Paso 2: asignar índices consecutivos
map<int, int> comp;
int idx = 0;
for (int x : unicos) comp[x] = idx++;

// Paso 3: reemplazar valores originales
for (int &x : v) x = comp[x];
// v = {2, 0, 1, 0, 2}

Esto es útil cuando necesitas usar los valores como índices de un arreglo pero son demasiado grandes.

Patrón 7: Grupo de claves compuestas

Usa map<pair<int,int>, int> o map<string, vector<int>> para agrupar:

// Agrupar puntos por distancia al origen
map<int, vector<pair<int,int>>> porDistancia;

int n;
cin >> n;
for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y;
    int dist = x*x + y*y;
    porDistancia[dist].push_back({x, y});
}

// Los puntos con la misma distancia al origen quedan agrupados

Resumen de cuándo usar qué

Ejercicio de práctica

Dado un arreglo de N números, encuentra la longitud del subarreglo contiguo más largo donde todos los elementos son distintos.

Entrada:

7
1 2 3 2 4 5 3

Salida: 4 (el subarreglo [2, 4, 5, 3] o [3, 2, 4, 5])

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

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int &x : v) cin >> x;

    set<int> ventana;
    int izq = 0, maxLen = 0;

    for (int der = 0; der < n; der++) {
        while (ventana.count(v[der])) {
            ventana.erase(v[izq]);
            izq++;
        }
        ventana.insert(v[der]);
        maxLen = max(maxLen, der - izq + 1);
    }

    cout << maxLen << endl;
    return 0;
}