← Estructuras de datos desde cero · Lección 6/32
Dos punteros y ventanas
Uno en cada punta
Muchos problemas de arreglos se resuelven con dos índices en vez de dos ciclos anidados. El más sencillo: uno empieza a la izquierda (i), otro a la derecha (j), y se acercan.
Para saber si una palabra es palíndromo (se lee igual al revés), comparas las puntas: si son iguales, los dos avanzan hacia el centro; si no, ya sabes que no lo es. Cada letra se mira una vez: O(n).
$ node leccion.js
Pulsa CORRER (o Ctrl+Enter).
Qué mirar
- «reconocer» compara cuatro parejas y llega al centro:
true. - «sahuayo» falla en la primera comparación (s contra o) y no sigue.
Toda la lección en una página
Uno en cada punta
Muchos problemas de arreglos se resuelven con dos índices en vez de dos ciclos anidados. El más sencillo: uno empieza a la izquierda (i), otro a la derecha (j), y se acercan.
Para saber si una palabra es palíndromo (se lee igual al revés), comparas las puntas: si son iguales, los dos avanzan hacia el centro; si no, ya sabes que no lo es. Cada letra se mira una vez: O(n).
function esPalindromo(texto) {
let i = 0, j = texto.length - 1;
while (i < j) {
console.log(" ", texto[i], "vs", texto[j]);
if (texto[i] !== texto[j]) return false;
i++;
j--;
}
return true;
}
console.log(esPalindromo("reconocer"));
console.log(esPalindromo("sahuayo"));
- «reconocer» compara cuatro parejas y llega al centro:
true. - «sahuayo» falla en la primera comparación (s contra o) y no sigue.
En un arreglo ordenado
Con un arreglo ordenado, dos punteros encuentran dos números que sumen un objetivo sin probar todas las parejas. Si la suma de las puntas se queda corta, mueves i a la derecha (un número más grande); si se pasa, mueves j a la izquierda (uno más chico).
Cada paso descarta un elemento para siempre, así que son a lo mucho n pasos en vez de n²/2 parejas. El orden es lo que permite descartar.
function parQueSuma(ordenado, objetivo) {
let i = 0, j = ordenado.length - 1;
while (i < j) {
const suma = ordenado[i] + ordenado[j];
console.log(" i =", i, "j =", j, "suma =", suma);
if (suma === objetivo) return [i, j];
if (suma < objetivo) i++; // falta: uno más grande
else j--; // sobra: uno más chico
}
return null;
}
console.log(parQueSuma([1, 3, 4, 6, 8, 11], 10));
1 + 11 = 12 se pasa y el 11 queda descartado; 1 + 8 = 9 se queda corto y sale el 1; 3 + 8 = 11 se pasa y sale el 8; 3 + 6 = 9 se queda corto y sale el 3; 4 + 6 = 10. Cinco pasos y responde [ 2, 3 ].
La ventana que se desliza
Otra forma de dos punteros: los dos van en la misma dirección y marcan una ventana [inicio, fin]. El fin avanza para meter elementos; el inicio avanza para sacarlos cuando la ventana deja de cumplir la condición.
Ejemplo: el tramo más largo de un texto sin letras repetidas. La ventana crece mientras no haya repetidas; cuando entra una repetida, el inicio se recorre hasta sacarla. Cada letra entra una vez y sale a lo mucho una vez: O(n).
function masLargoSinRepetir(s) {
const dentro = new Set();
let inicio = 0, mejor = 0;
for (let fin = 0; fin < s.length; fin++) {
while (dentro.has(s[fin])) { // repetida: encoger por la izquierda
dentro.delete(s[inicio]);
inicio++;
}
dentro.add(s[fin]);
mejor = Math.max(mejor, fin - inicio + 1);
console.log(" ventana:", s.slice(inicio, fin + 1));
}
return mejor;
}
console.log(masLargoSinRepetir("abcabcbb"));
La ventana crece a «abc», y cada vez que entra una letra repetida suelta la de la izquierda: «bca», «cab», «abc»… La mejor mide 3.