Dos punteros y ventana deslizante
Tema: Estructuras de Datos · temarios: Syllabus OCI · Syllabus IOI
📍 Dónde se aprende: módulo 17 de la Ruta de Aprendizaje.
Qué hace
Recorre la secuencia con dos índices que solo avanzan, manteniendo un segmento (la ‘ventana’) que cumple una condición. Reemplaza un doble ciclo O(n²) por una sola pasada.
Complejidad: O(n) amortizado: cada puntero recorre el arreglo a lo más una vez en total, aunque una iteración mueva varios pasos.
Cuándo usarlo
Subarreglo más corto/largo que cumple algo (suma ≥ K, a lo más k distintos), contar pares en un arreglo ordenado, emparejar extremos. Requisito: al mover el extremo derecho la condición debe cambiar de forma monótona. Aparece en la práctica del módulo 17 de la Ruta de Aprendizaje.
Implementación recomendada (C++)
// subarreglo más corto con suma >= objetivo (valores no negativos)
int ventana(const vector<int>& a, long long objetivo) {
int mejor = INT_MAX, ini = 0;
long long suma = 0;
for (int fin = 0; fin < (int)a.size(); fin++) {
suma += a[fin]; // crece por la derecha
// el ini < fin evita que la ventana se vacíe (y que ini se salga del
// arreglo) cuando objetivo <= 0 o hay ceros al principio
while (ini < fin && suma - a[ini] >= objetivo) suma -= a[ini++];
if (suma >= objetivo) mejor = min(mejor, fin - ini + 1);
}
return mejor == INT_MAX ? -1 : mejor;
}⚠️ Notas
Con valores negativos la ventana deja de ser monótona y esto no sirve: ahí toca prefijos + map. Para el máximo o el mínimo de cada ventana de largo fijo, usa la deque monótona (deque). El costo O(n) sale del argumento amortizado explicado en Complejidad computacional.