Two pointers& sliding window
Dos formas de no recalcular lo que ya sabes.
Jueves 15 de octubre · 14:00 – 16:00
Esto ya lo conocen.
No lo expliques de nuevo.
Salir con dos formas de no recalcular lo que ya sabes…
…y con el hábito de preguntarse qué cambia entre un paso y el siguiente.
¿Cuántas sumas tienes que hacer para encontrar el mejor bloque de 3 números consecutivos…
…en 100,000 elementos?
¿Qué cambia de un bloque al siguiente?
¿Cuál es la suma máxima de un bloque de tamaño k?
La forma directa: sumar cada bloque desde cero.
int mejor = -1000000000;
for (int i = 0; i + k <= n; i++) {
int suma = 0;
for (int j = i; j < i + k; j++)
suma += a[j];
if (suma > mejor)
mejor = suma;
}
cout << mejor << "\n";¿Cuántas operaciones hace esto, aproximadamente?
Cada bloque se suma completo otra vez, aunque casi todo se repite.
Una suma y una resta por paso, sin importar cuánto mida el bloque.
int suma = 0;
for (int j = 0; j < k; j++)
suma += a[j];
int mejor = suma;
for (int i = k; i < n; i++) {
suma += a[i]; // entra a[i]
suma -= a[i - k]; // sale a[i - k]
if (suma > mejor)
mejor = suma;
}
cout << mejor << "\n";Primero el bloque inicial: k.
Después un solo ciclo de n, con dos operaciones por paso.
Ventana fija: el tamaño no cambia, la ventana solo se desliza.
Restar el elemento equivocado.
Pregunta de control: si k = 3 y estás en i = 5, ¿qué elemento sale?
Sale a[2], no a[3].
¿Y si el tamaño de la ventana no es fijo?
¿Cuál es el subarreglo más largo cuya suma no pasa de S?
Tamaño variable: no puedes saber de antemano cuánto mide la respuesta.
Para probar cada longitud habría que revisar todos los subarreglos:
Agrandas por la derecha mientras cabe; cuando no cabe, achicas por la izquierda.
int izq = 0;
long long suma = 0;
int mejor = 0;
for (int der = 0; der < n; der++) {
suma += a[der];
while (suma > S) {
suma -= a[izq];
izq++;
}
if (der - izq + 1 > mejor)
mejor = der - izq + 1;
}
cout << mejor << "\n";¿Qué pasa si cambias while por if?
Sin responder todavía. Lo retomamos más adelante.
¿Siempre funciona la ventana variable?
Con números negativos, sacar un elemento puede aumentar la suma, y el criterio de encoger deja de servir.
El criterio de esta clase asume elementos positivos.
¿Cuántas veces se mueve cada puntero en total?
Cada extremo solo avanza hacia la derecha, nunca retrocede. Cada uno se mueve a lo más n veces.
Dos punteros que avanzan en la misma dirección y nunca retroceden.
Un par que suma X
Dos extremos que caminan el uno hacia el otro.
En un arreglo ordenado, ¿hay dos números que sumen X?
Lo directo son todos los pares:
Si el arreglo está ordenado, puedes descartar pares completos.
Si la suma actual es mayor que X, ¿qué conviene mover?
El extremo derecho es el más grande; el izquierdo, el más chico.
int i = 0, j = n - 1;
while (i < j) {
long long s = a[i] + a[j];
if (s == X) {
cout << a[i] << " " << a[j] << "\n";
return 0;
}
if (s < X)
i++;
else
j--;
}
cout << "No hay\n";Cada paso mueve un puntero hacia el centro. Como mucho n pasos.
+ el costo de sort que ya conocen.
Un arreglo ordenado permite descartar pares, no solo mirarlos.
Dos parejas que se confunden
La mayoría piensa que dos punteros siempre significa ventana.
¿El par que suma X es un bloque contiguo?
Entrada: a = 1 1 1 4 S = 3
¿Cuántas veces tienes que encoger aquí?
La ventana sigue inválida y el programa sigue contando sobre ella. El while existe por esto.
Suma máxima de k consecutivos
ventana fijaPractica el paso de restar y sumar.
Par que suma X en arreglo ordenado
two pointersPractica mover el puntero correcto.
Número de bloques con suma exacta S
ventana · positivosPractica la condición de encoger.
Los nombres son referencias: búscalos en omegaUp.
Subarreglo más largo con suma ≤ S
Ventana variable completa.
Triples con suma cero en arreglo ordenado
Un ciclo fijo y two pointers adentro. ¿Complejidad? O(n²), no O(n³).
Bloque más corto con suma ≥ S
Ventana variable en sentido contrario: encoger cuando ya se cumple.
El 4, con restricción
Solo for, while y una función cabe(). Sin sort, sin vectores auxiliares.
¿Por qué la ventana variable es O(n) aunque tenga un while adentro del for?
Cada puntero se mueve a lo más n veces en total, no por iteración del for.
1 – 3 obligatorios · 4 y 5 recomendados · 6 y 7 reto
Club de Programación Competitiva