Two Pointers y Sliding Window: Técnicas para optimizar arreglos y cadenas

1. Descripción general

Cuando enfrentas un problema que requiere recorrer un arreglo o cadena y la solución brute-force ejecuta O(n²) u O(n³), dos técnicas two pointers y sliding window te ayudan a reducir la complejidad a O(n). Este artículo explica la idea central de cada técnica, con ejemplos Java concretos: two sum en un arreglo ordenado, verificación de palindrome, suma máxima de un subarreglo dentro de una ventana fija, y substring más largo sin caracteres repetidos. Al terminar, reconocerás el patrón y podrás aplicarlo a muchos problemas similares.

2. ¿Qué es Two Pointers?

Two pointers es una técnica que utiliza dos variables de índice (punteros) que se desplazan sobre una estructura de datos (generalmente un arreglo o cadena ordenada) para evitar recorridos anidados. Los dos punteros pueden moverse:

• En la misma dirección (fast/slow): se usa para eliminar elementos duplicados, detectar ciclos.
• En direcciones opuestas (left/right desde ambos extremos): se usa para encontrar un par con suma igual al target, verificar palindrome.

2.1. Two pointers en direcciones opuestas: encontrar un par con suma igual al target

Problema clásico: dado un arreglo ordenado en forma ascendente, encuentra dos números cuya suma sea igual al target.

public class TwoSumSorted {

    public int[] findPair(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{numbers[left], numbers[right]};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[0];
    }
}

Explicación:

• left comienza desde el inicio del arreglo, right desde el final.
• Si sum < target, el número en left es demasiado pequeño, así que aumenta left para obtener un número más grande.
• Si sum > target, el número en right es demasiado grande, así que disminuye right.
• El bucle ejecuta como máximo n pasos porque en cada iteración left o right se desplaza una posición, resultando en una complejidad O(n) en lugar de O(n²) del enfoque con dos bucles anidados.

Prueba con JUnit 5 + AssertJ:

<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>5.10.2</version>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.assertj</groupId>
    <artifactId>assertj-core</artifactId>
    <version>3.25.3</version>
    <scope>test</scope>
</dependency>

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class TwoSumSortedTest {

    private final TwoSumSorted twoSum = new TwoSumSorted();

    @Test
    void shouldFindPairWhenSumMatchesTarget() {
        int[] numbers = {1, 3, 5, 8, 11};

        int[] result = twoSum.findPair(numbers, 13);

        assertThat(result).containsExactly(5, 8);
    }
}

Nota: esta técnica requiere que el arreglo esté ordenado. Si el arreglo aún no está ordenado, debes ordenarlo primero (O(n log n)) o usar un HashMap para mantener O(n) sin necesidad de ordenar.

2.2. Two pointers para verificar palindrome

public class PalindromeChecker {

    public boolean isPalindrome(String text) {
        int left = 0;
        int right = text.length() - 1;

        while (left < right) {
            if (text.charAt(left) != text.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

Los dos punteros comienzan desde ambos extremos de la cadena, comparan caracteres y avanzan hacia el centro. Si encuentran un par de caracteres diferentes, devuelven false inmediatamente — sin necesidad de recorrer todo. Esta es la razón por la que esta técnica es más rápida que invertir la cadena y luego comparar (reverse().equals()), ya que evita crear un objeto StringBuilder intermedio.

3. ¿Qué es Sliding Window?

Sliding window es una variante de two pointers que se aplica a problemas relacionados con subarreglos/subcadenas consecutivos. En lugar de recalcular desde el principio para cada posición inicial, mantienes una “ventana” [left, right] y la actualizas gradualmente mientras la ventana se desliza, reutilizando los cálculos anteriores.

Hay dos tipos:

• Fixed-size window: el tamaño de la ventana es fijo (por ejemplo, k elementos).
• Variable-size window: el tamaño se ajusta dinámicamente según la condición del problema.

3.1. Fixed-size window: suma máxima de un subarreglo de tamaño k

public class MaxSumSubarray {

    public int maxSum(int[] numbers, int windowSize) {
        int windowSum = 0;
        for (int i = 0; i < windowSize; i++) {
            windowSum += numbers[i];
        }

        int maxSum = windowSum;
        for (int right = windowSize; right < numbers.length; right++) {
            windowSum += numbers[right] - numbers[right - windowSize];
            maxSum = Math.max(maxSum, windowSum);
        }
        return maxSum;
    }
}

Explicación:

• El primer bucle calcula la suma de la primera ventana (desde el índice 0 hasta windowSize - 1).
• A partir de ahí, cada vez que desplazas la ventana un paso hacia la derecha: sumas el nuevo elemento (numbers[right]), restas el elemento que salió de la ventana (numbers[right - windowSize]).
• Gracias a esto, cada paso cuesta O(1) en lugar de recalcular la suma en O(k), resultando en una complejidad total de O(n).

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class MaxSumSubarrayTest {

    private final MaxSumSubarray solver = new MaxSumSubarray();

    @Test
    void shouldReturnMaxSumOfWindowSizeThree() {
        int[] numbers = {2, 1, 5, 1, 3, 2};

        int result = solver.maxSum(numbers, 3);

        assertThat(result).isEqualTo(9); // ventana [5, 1, 3]
    }
}

3.2. Variable-size window: substring más largo sin caracteres repetidos

Bài này cửa sổ co giãn tùy điều kiện “không có ký tự lặp”.

import java.util.HashMap;
import java.util.Map;

public class LongestUniqueSubstring {

    public int lengthOfLongestSubstring(String text) {
        Map<Character, Integer> lastSeenIndex = new HashMap<>();
        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < text.length(); right++) {
            char current = text.charAt(right);
            if (lastSeenIndex.containsKey(current) && lastSeenIndex.get(current) >= left) {
                left = lastSeenIndex.get(current) + 1;
            }
            lastSeenIndex.put(current, right);
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}

Explicación:

• right siempre avanza (expande la ventana), left solo salta cuando encuentra un carácter repetido dentro de la ventana actual.
• lastSeenIndex almacena la posición más reciente de cada carácter para saber a dónde debe saltar left.
• La condición lastSeenIndex.get(current) >= left garantiza que solo se considere “repetido” si el carácter aún está dentro de la ventana actual, evitando que left retroceda incorrectamente.
• Cada carácter se procesa exactamente una vez en right, por lo que la complejidad total es O(n).

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class LongestUniqueSubstringTest {

    private final LongestUniqueSubstring solver = new LongestUniqueSubstring();

    @Test
    void shouldReturnLengthOfLongestUniqueSubstring() {
        int result = solver.lengthOfLongestSubstring("abcabcbb");

        assertThat(result).isEqualTo(3); // "abc"
    }

    @Test
    void shouldHandleAllSameCharacters() {
        int result = solver.lengthOfLongestSubstring("bbbbb");

        assertThat(result).isEqualTo(1);
    }
}

Salida al depurar manualmente con "abcabcbb":

right=0 'a' -> ventana="a"    longitud=1
right=1 'b' -> ventana="ab"   longitud=2
right=2 'c' -> ventana="abc"  longitud=3
right=3 'a' -> repetido, left=1 -> ventana="bca" longitud=3
right=4 'b' -> repetido, left=2 -> ventana="cab" longitud=3
...
maxLength = 3

4. Comparación y cuándo usar cada técnica

Situación	Técnica apropiada
Arreglo ordenado, encontrar par/terna que cumple condición de suma	Two pointers en direcciones opuestas
Verificar simetría (palindrome), invertir arreglo in-place	Two pointers en direcciones opuestas
Eliminar elementos duplicados en un arreglo ordenado	Two pointers en la misma dirección (fast/slow)
Subarreglo/substring de tamaño fijo k	Sliding window de tamaño fijo
Subarreglo/substring que cumple una condición dinámica (sin repeticiones, suma ≤ target, etc.)	Sliding window de tamaño variable

Punto en común: ambas técnicas evitan recalcular las partes ya procesadas, reduciendo la complejidad de O(n²) a O(n) manteniendo el estado (sum, set, map) mientras los punteros/ventanas se desplazan.

5. Errores comunes

• Olvidar la condición de parada left < right: fácilmente causa bucles infinitos o compara un elemento consigo mismo cuando left == right.
• Aplicar two pointers a un arreglo no ordenado sin olvidar ordenar primero — los resultados serán completamente incorrectos porque la lógica de incremento/decremento del puntero depende de la monotonía del arreglo.
• En sliding window, olvidar actualizar el estado cuando left se desplaza: por ejemplo, olvidar eliminar el elemento anterior del HashMap/sum, causando que la ventana “recuerde” datos que ya no están dentro de ella.
• Confundir la condición de expansión/contracción de la ventana: con variable-size window, debes identificar claramente qué condición hace que right avance y cuál hace que left avance — si las inviertes, la ventana nunca se contraerá correctamente.

Nota: estas dos técnicas no son apropiadas cuando el problema requiere considerar toda combinación de subconjuntos no consecutivos (como subset sum) — en esos casos necesitas backtracking o dynamic programming, no sliding window.

6. Conclusión

Two pointers y sliding window son dos herramientas fundamentales para resolver problemas de arreglos/cadenas con complejidad lineal. Identificar el patrón — si necesitas encontrar un par en un arreglo ordenado, o si necesitas optimizar un subarreglo/substring consecutivo — te ayuda a elegir la técnica correcta y escribir código conciso y fácil de probar como los ejemplos anteriores. Cuando practiques, intenta trazar manualmente el estado de left/right en cada paso para comprender bien el invariante antes de codificar.