Técnica de dos punteros y ventana deslizante explicada

Qué problema resuelven estas técnicas

Muchos problemas de arreglos y cadenas preguntan por pares o rangos contiguos: dos números que suman un objetivo, la subcadena más larga sin caracteres repetidos, el subarreglo más corto con suma de al menos k. Revisar todos los pares o todos los rangos cuesta O(n²) o más. Los dos punteros lo evitan aprovechando una propiedad de los datos, como el orden o el hecho de que la ventana solo necesita pequeñas actualizaciones, para descartar muchos candidatos de golpe.

Punteros en extremos opuestos: suma de un par en un arreglo ordenado

Encuentra dos números de la lista ordenada [1, 3, 4, 6, 8, 11] cuya suma sea 10. Empieza con el menor y el mayor. Si la suma es demasiado pequeña, la única forma de aumentarla es mover left a la derecha; si es demasiado grande, mueve right a la izquierda.

def pair_with_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return left, right
        if s < target:
            left += 1
        else:
            right -= 1
    return None
print(pair_with_sum([1, 3, 4, 6, 8, 11], 10))   # (2, 3)
print(pair_with_sum([1, 3, 4, 6, 8, 11], 2))    # None

Cada paso mueve un puntero hacia dentro, así que hay como máximo n − 1 pasos: O(n) de tiempo y O(1) de espacio. La misma forma comprueba si una cadena es un palíndromo, invierte un arreglo in situ y, dentro de un bucle exterior, resuelve 3Sum en O(n²) en lugar de O(n³).

Punteros rápido y lento: filtrado in situ

Un puntero lento marca dónde debe ir el siguiente elemento que se conserva; un puntero rápido recorre todos los elementos. Así se eliminan los duplicados de una lista ordenada sin memoria adicional.

def dedupe_sorted(nums):
    """Remove duplicates in place; return the new length."""
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1
a = [1, 1, 2, 3, 3, 3, 5]
k = dedupe_sorted(a)
print(k, a[:k])   # 4 [1, 2, 3, 5]

En listas enlazadas, el puntero rápido avanza dos nodos por paso y el lento uno. Si llegan a encontrarse, la lista tiene un ciclo (detección de ciclos de Floyd); cuando el puntero rápido llega al final, el lento está en el medio.

Ventana deslizante: subcadena más larga sin repeticiones

Una ventana deslizante mantiene válido el rango s[left:right + 1]. Avanza right un carácter cada vez. Cuando el nuevo carácter rompe la regla, avanza left hasta que la ventana vuelva a ser válida. Registra la mejor ventana sobre la marcha.

def longest_unique(s):
    last_seen = {}          # char -> last index
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1   # jump past the repeat
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best
print(longest_unique("abcabcbb"))   # 3  ("abc")
print(longest_unique("pwwkew"))     # 3  ("wke")
print(longest_unique(""))           # 0

Las ventanas son de dos tipos. Una ventana de tamaño fijo de k elementos añade el elemento que entra por la derecha y quita el que sale por la izquierda, por ejemplo para calcular una media móvil. Una ventana de tamaño variable crece y se encoge para cumplir una condición, como arriba.

def min_len_subarray(nums, k):
    """Shortest subarray with sum >= k (non-negative nums)."""
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= k:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best
print(min_len_subarray([2, 3, 1, 2, 4, 3], 7))   # 2  ([4, 3])

Complejidad temporal y espacial

La razón por la que una ventana deslizante es O(n) incluso con un bucle while anidado: left y right avanzan cada uno como máximo n veces en total, así que el trabajo total es como mucho 2n pasos.

Errores comunes

• Usar punteros en extremos opuestos con datos sin ordenar. La decisión de mover left o right solo es correcta porque el arreglo está ordenado.
• Usar una ventana deslizante basada en sumas cuando los números pueden ser negativos. Reducir la ventana ya no disminuye siempre la suma; usa en su lugar sumas de prefijos con un mapa hash.
• Longitud de la ventana con desfase de uno: la ventana left..right, ambos incluidos, tiene right - left + 1 elementos.
• Olvidar detenerse en left < right, lo que permite que un único elemento forme pareja consigo mismo.
• Mover left hacia atrás. En el ejemplo de la subcadena, la comprobación last_seen[ch] >= left evita saltar a una posición antigua.

Cuándo usarlas y preguntas típicas de entrevista

Recurre a dos punteros cuando la entrada esté ordenada (o se pueda ordenar a bajo coste) y busques pares, o cuando necesites modificar un arreglo in situ. Recurre a una ventana deslizante cuando el enunciado hable de subarreglo o subcadena contigua y pida el más largo, el más corto, el máximo o un recuento con una condición que cambia de forma predecible al crecer la ventana. Si los datos no están ordenados y necesitas un par, un conjunto hash suele ser más simple y también O(n).

• Two Sum II (entrada ordenada), 3Sum, Container With Most Water, Trapping Rain Water.
• Valid Palindrome, Reverse String, Move Zeroes, Remove Duplicates from Sorted Array.
• Longest Substring Without Repeating Characters, Minimum Window Substring, Sliding Window Maximum (con una deque).
• Linked List Cycle, Middle of the Linked List.

Fuera de las entrevistas, las mismas ideas aparecen al combinar archivos ordenados, en protocolos de red que llevan una ventana de paquetes sin confirmar (ventana deslizante de TCP), en limitadores de tasa que cuentan eventos de los últimos N segundos y en medias móviles de series temporales.