Dos punteros y ventana deslizante

De qué trata este capítulo

Muchísimos problemas de arrays y strings tienen una solución obvia en O(n²) — para cada punto de inicio, recorre hacia adelante — y otra mucho mejor en O(n) que casi nadie ve a la primera. La técnica que desbloquea la versión lineal son los dos punteros: en lugar de un ciclo anidado, mueves dos índices a lo largo de los datos y mantienes la ventana entre ellos de forma incremental, actualizando solo lo que cambia conforme la ventana se desliza en vez de recalcularla desde cero. Es la misma idea del rolling hash, generalizada como patrón de diseño. Este capítulo cubre las tres formas que toma — una ventana deslizante de tamaño variable (el substring más largo sin caracteres repetidos), el recorrido con dos punteros desde ambos extremos (un par que suma un valor objetivo en un array ordenado) y una ventana deslizante de tamaño fijo (suma máxima de k elementos consecutivos) — y muestra la recompensa: en el problema del substring único más largo, la ventana deslizante hace 400 veces menos trabajo que la fuerza bruta con longitud 800, porque cada índice solo avanza.

Un poco de historia

Los dos punteros y la ventana deslizante no tienen un inventor único ni un origen célebre — son técnicas folclóricas, ese tipo de idea que se redescubre a cada rato porque es la optimización natural en cuanto notas que un ciclo anidado está rehaciendo trabajo. Su salto a la fama tiene más que ver con la pedagogía que con la historia: conforme las entrevistas algorítmicas se estandarizaron en los 2000 y 2010, estos patrones se volvieron de los más enseñados y evaluados, justo porque capturan una idea transferible — reconocer cuándo un recorrido cuadrático esconde una estructura lineal. Eso sí, el principio de fondo es viejo y profundo: es la misma idea de amortización que hace lineal el recorrido de KMP (un puntero que solo avanza), el rolling hash O(1) por deslizamiento (actualiza, no recalcules) y los appends del array dinámico O(1) (un costo ocasional repartido entre muchas operaciones). La ventana deslizante es ese principio aplicado al omnipresente problema de "examinar todos los rangos contiguos", y su valor está tanto en entrenar el ojo para ver la solución lineal como en el código mismo.

La intuición

Toma el problema estrella: el substring más largo sin caracteres repetidos. En abcabcbb, la respuesta es abc, longitud 3. La fuerza bruta prueba cada posición inicial y extiende hasta toparse con una repetición — O(n²), y vuelve a examinar los mismos caracteres una y otra vez entre inicios que se traslapan. La ventana deslizante lo resuelve en una sola pasada con dos punteros que marcan la ventana actual [left, right]. Avanza right un carácter a la vez, extendiendo la ventana. El invariante de la ventana es "no hay caracteres repetidos dentro de ella". Cuando el nuevo carácter en right es uno que ya está en la ventana actual, el invariante se rompería — así que salta left hacia adelante, justo después de la ocurrencia anterior de ese carácter, lo cual restaura el invariante descartando la parte vieja de la ventana. Lleva registro de la ventana más grande vista. Ambos punteros solo se mueven hacia adelante, nunca hacia atrás, así que el trabajo total es O(n) aunque la ventana crezca y se encoja.

Las otras dos formas comparten la idea de "dos índices, estado incremental" en geometrías distintas. El recorrido con dos punteros funciona sobre un array ordenado: para encontrar un par que sume un objetivo, arranca con un puntero en cada extremo. Si la suma actual es muy chica, la única forma de aumentarla es mover el puntero bajo hacia la derecha (hacia valores más grandes); si es muy grande, mueve el puntero alto hacia la izquierda. Cada movimiento elimina un valor de la jugada, así que el par se encuentra (o se descarta) en O(n) — sin ciclo anidado, sin hash set. La ventana de tamaño fijo desliza una ventana de ancho constante sobre los datos para calcular algo como la suma máxima de k elementos consecutivos: calcula la suma de la primera ventana una vez y luego, en cada deslizamiento, suma el elemento que entra y resta el que sale, O(1) por paso en vez de volver a sumar k elementos. Las tres reemplazan un ciclo anidado por un barrido, y el truco común es que el estado de la ventana (el conjunto de caracteres, la suma acumulada, las posiciones de los punteros) se arrastra a través del deslizamiento y se actualiza barato, nunca se reconstruye.

Complejidad: cómo escala

La ventana deslizante es O(n): el puntero derecho visita cada elemento una vez, y el izquierdo solo avanza, así que su movimiento combinado es a lo mucho 2n — un argumento amortizado idéntico al de KMP. La fuerza bruta es O(n²) en el peor caso (un string con todos los caracteres distintos, donde cada inicio se extiende hasta el final). El enfrentamiento cuenta operaciones exactamente sobre ese peor caso conforme crece la entrada:

En una gráfica log-log la línea de la fuerza bruta tiene pendiente 2 (cuadrática) y la de la ventana deslizante pendiente 1 (lineal) — se separan sin límite. Con longitud 800, la ventana deslizante hizo 800 operaciones (una por carácter) mientras que la fuerza bruta hizo alrededor de 320,000 — una diferencia de 400 veces, y la razón crece linealmente con la entrada, así que con longitud 8,000 sería de 4,000 veces. Esta es la forma recurrente de estas técnicas: no recortan un factor constante, tumban un factor entero de n, convirtiendo un recorrido que se ahoga con entradas grandes en uno que pasa volando. El estado incremental de la ventana es lo que lo compra — la fuerza bruta vuelve a leer regiones traslapadas que la ventana maneja una sola vez.

En qué es buena y en qué no

Las técnicas de dos punteros y ventana deslizante son la herramienta correcta para problemas sobre rangos contiguos (subarrays, substrings) o pares/tríos en datos ordenados, siempre que la propiedad objetivo se pueda mantener incrementalmente conforme la ventana se mueve. Los usos canónicos: el subarray o substring más largo/corto que cumple una condición (sin repeticiones, a lo mucho k distintos, suma ≥ objetivo, que contenga un conjunto requerido), problemas de suma de pares y tríos en arrays ordenados (two-sum, three-sum, par más cercano), estadísticas de ventana fija (promedios móviles, máx/mín sobre una ventana), mezcla de secuencias ordenadas y particionado (el partition de quicksort y la bandera holandesa son de dos punteros). Convierten muchísimas fuerzas brutas O(n²) en O(n) u O(n log n) (con un sort), y por eso son tan socorridas.

Donde no aplican es cuando la propiedad no es monótona en la ventana — cuando encoger desde la izquierda podría después obligar a volver a expandir, el barrido simple da respuestas incorrectas y necesitas una estructura más pesada (un deque monótono, prefix-sums con hash map, un árbol balanceado). El clásico truco: suma-de-subarray-igual-a-objetivo con números negativos, donde la suma de la ventana no es monótona conforme la extiendes, así que el enfoque de dos punteros falla y en su lugar necesitas un hash map de prefix-sums. La variante de dos extremos requiere entrada ordenada, así que cuesta un sort O(n log n) si los datos no vienen ya ordenados. Y estas son técnicas para estructura lineal, no un sustituto de los demás paradigmas — los problemas que necesitan búsqueda global (backtracking) u optimización con subproblemas traslapados (DP) no tienen forma de ventana deslizante. La precondición — estado de ventana monótono y mantenible incrementalmente — es lo que hay que revisar antes de echar mano de ellas.

Los datos, o las entradas

El enfrentamiento cuenta operaciones para el problema del substring único más largo — la ventana deslizante contra la fuerza bruta de ciclos anidados — sobre entradas con todos los caracteres distintos (el peor caso O(n²) de la fuerza bruta) conforme crece la longitud. La correctitud se verifica con miles de casos aleatorios en las tres técnicas: la longitud de la ventana deslizante debe coincidir con la de la fuerza bruta y el substring que devuelve debe estar genuinamente libre de repeticiones y presente en el string; el par de la técnica de dos punteros debe coincidir con la búsqueda de pares por fuerza bruta (encontrando un par válido exactamente cuando existe); y el máximo de la ventana fija debe coincidir con volver a sumar cada ventana. La animación desliza la ventana sobre abcabcbb, mostrando los punteros izquierdo y derecho y el salto del izquierdo cada vez que entra un carácter repetido.

Constrúyelo, una función a la vez

La ventana deslizante de tamaño variable — el substring más largo sin repeticiones:

def longest_unique_substring(s, trace=None):
    """Longest substring with no repeated character, in one pass. `last` remembers each character's
    most recent index. Extend the window's right edge over every character; when the new character
    was already seen INSIDE the current window, jump the left edge just past that previous
    occurrence (shrinking the window to stay duplicate-free). Track the largest window. O(n): each
    index moves forward only, never back. Returns (length, the substring)."""
    last = {}
    left = 0
    best_len, best_l = 0, 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1                   # contract: skip past the duplicate
        last[ch] = right
        if right - left + 1 > best_len:
            best_len, best_l = right - left + 1, left
        if trace is not None:
            trace.append((left, right, best_len))
    return best_len, s[best_l:best_l + best_len]

El recorrido de dos punteros desde ambos extremos — un par que suma un objetivo en datos ordenados:

def two_sum_sorted(nums, target):
    """In a SORTED array, find two values summing to `target`, using two pointers from the ends. If
    the current sum is too small, move the left pointer right (only larger values remain that way);
    if too large, move the right pointer left. Each step discards one candidate, so it's O(n) — no
    nested loop, no hash set. Returns the (i, j) indices, or None."""
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return (lo, hi)
        if s < target:
            lo += 1                               # need a bigger sum → raise the low end
        else:
            hi -= 1                               # need a smaller sum → lower the high end
    return None

La ventana deslizante de tamaño fijo — suma máxima de k elementos consecutivos, O(1) por deslizamiento:

def max_window_sum(nums, k):
    """Maximum sum of any k consecutive elements, by sliding a fixed-width window: compute the first
    window's sum, then for each step add the entering element and subtract the leaving one — O(1)
    per slide instead of re-summing k elements. O(n) total. Returns the best sum."""
    if k > len(nums) or k <= 0:
        return None
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]           # roll: +entering, -leaving
        best = max(best, window)
    return best

Míralo funcionar

Aquí está la ventana deslizante encontrando el substring más largo sin repeticiones de abcabcbb. La celda verde es el borde izquierdo de la ventana, la naranja es el borde derecho, y las celdas azules entre ellas son la ventana actual. Observa cómo el puntero derecho marcha hacia adelante, extendiendo la ventana: a, ab, abc — longitud 3. Luego el siguiente carácter es otra a, que ya está en la ventana (parpadea en rojo) — así que el puntero izquierdo salta hacia adelante pasando esa a vieja, encogiendo la ventana para mantenerla libre de repeticiones. La ventana se desliza, expandiéndose cuando puede y contrayéndose cuando un duplicado la obliga, sin mover jamás ninguno de los dos punteros hacia atrás. La ventana más grande que llega a sostener — abc, longitud 3 — es la respuesta. Cada carácter es visitado una vez por el puntero derecho y a lo mucho una vez por el izquierdo, y por eso todo el barrido es lineal:

El código completo

La pestaña desde cero trae las tres técnicas — ventana variable, recorrido de dos punteros, ventana fija; la pestaña de librería trae la versión por fuerza bruta O(n²) de cada una, usada para verificar correctitud y como línea base en el enfrentamiento. Cámbiate entre ellas — las fuerzas brutas son más cortas y obviamente correctas, y esa obviedad cuadrática es justo la trampa de la que escapan las técnicas lineales.

"""Two pointers and sliding window — turn many O(n^2) scans into a single O(n) pass by moving two
indices through the data and maintaining a window's state incrementally instead of recomputing it
from scratch. The insight is the same one behind the rolling hash: when a window slides, most of it
is unchanged, so update the little that changed rather than re-examine the whole thing.

Three shapes cover most uses. A VARIABLE-size sliding window grows its right edge and shrinks its
left edge to maintain a property — like the longest substring with no repeated character, where the
right pointer extends the window and the left pointer jumps forward whenever a duplicate appears.
The TWO-POINTER shape walks two indices from opposite ends of a sorted array toward each other — like
finding a pair that sums to a target, moving the pointer that brings the sum closer. A FIXED-size
window slides a constant-width window across the data, adding the entering element and removing the
leaving one in O(1). All three replace a nested loop with a single sweep, and the trick is always to
carry state across the slide instead of rebuilding it.
"""


# region: sliding_window
def longest_unique_substring(s, trace=None):
    """Longest substring with no repeated character, in one pass. `last` remembers each character's
    most recent index. Extend the window's right edge over every character; when the new character
    was already seen INSIDE the current window, jump the left edge just past that previous
    occurrence (shrinking the window to stay duplicate-free). Track the largest window. O(n): each
    index moves forward only, never back. Returns (length, the substring)."""
    last = {}
    left = 0
    best_len, best_l = 0, 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1                   # contract: skip past the duplicate
        last[ch] = right
        if right - left + 1 > best_len:
            best_len, best_l = right - left + 1, left
        if trace is not None:
            trace.append((left, right, best_len))
    return best_len, s[best_l:best_l + best_len]
# endregion


# region: two_pointer
def two_sum_sorted(nums, target):
    """In a SORTED array, find two values summing to `target`, using two pointers from the ends. If
    the current sum is too small, move the left pointer right (only larger values remain that way);
    if too large, move the right pointer left. Each step discards one candidate, so it's O(n) — no
    nested loop, no hash set. Returns the (i, j) indices, or None."""
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return (lo, hi)
        if s < target:
            lo += 1                               # need a bigger sum → raise the low end
        else:
            hi -= 1                               # need a smaller sum → lower the high end
    return None
# endregion


# region: fixed_window
def max_window_sum(nums, k):
    """Maximum sum of any k consecutive elements, by sliding a fixed-width window: compute the first
    window's sum, then for each step add the entering element and subtract the leaving one — O(1)
    per slide instead of re-summing k elements. O(n) total. Returns the best sum."""
    if k > len(nums) or k <= 0:
        return None
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]           # roll: +entering, -leaving
        best = max(best, window)
    return best
# endregion

"""The contrast: the O(n^2) (or worse) brute-force versions the linear techniques replace. These are
the correctness references AND the baselines the face-off times against. There's no single stdlib
call for these problems — two pointers and sliding window are techniques, not library functions —
so the 'library' here is the naive nested-loop way you'd write without the technique.
"""


# region: brute
def longest_unique_brute(s):
    """Longest substring with no repeat, the obvious way: for every start index, extend until a
    repeat, tracking the best. O(n^2) — it re-scans overlapping regions the sliding window handles
    in one pass. The correctness reference and the baseline."""
    best = 0
    n = len(s)
    for i in range(n):
        seen = set()
        for j in range(i, n):
            if s[j] in seen:
                break
            seen.add(s[j])
        best = max(best, len(seen))
    return best


def two_sum_brute(nums, target):
    """Check every pair — O(n^2). Returns a matching (i, j) with i < j, or None."""
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return (i, j)
    return None


def max_window_sum_brute(nums, k):
    """Re-sum every window from scratch — O(n·k). The baseline the O(1)-slide beats."""
    if k > len(nums) or k <= 0:
        return None
    best = None
    for i in range(len(nums) - k + 1):
        s = sum(nums[i:i + k])
        best = s if best is None else max(best, s)
    return best
# endregion

Desde cero vs librería

Estas técnicas enseñan más una forma de ver que un algoritmo específico: cuando detectes un ciclo anidado que vuelve a examinar rangos traslapados, pregúntate si el trabajo interno se puede mantener incrementalmente mientras una ventana externa se desliza — y si la propiedad es monótona, normalmente sí se puede, colapsando O(n²) a O(n). Es la misma idea de reutilización amortizada que atravesó el rolling hash, el recorrido sin retroceso de KMP y los appends del array dinámico, ahora empaquetada como un patrón reutilizable para la enorme clase de problemas de rangos contiguos y pares ordenados. La brecha de 400 veces del enfrentamiento es lo que compra esa reutilización. No hay llamada de librería porque es una técnica, no una función — y precisamente por eso vale la pena interiorizarla: la habilidad está en reconocer la forma de ventana deslizante en un problema que no se anuncia como tal, y en conocer la precondición de monotonía que te dice que es seguro. Construir tú mismo las tres formas es lo que entrena ese reconocimiento.

Dónde te lo vas a encontrar de verdad

La ventana deslizante y los dos punteros aparecen por todos lados, en sistemas y en código del día a día. El procesamiento de streams y series de tiempo calcula promedios móviles, rate limits y agregados por ventana con ventanas fijas (monitoreo de red, datos de ticks financieros, suavizado de sensores). El procesamiento de texto y la búsqueda usan ventanas variables para problemas de substrings y n-gramas. La búsqueda de pares y tríos en datos ordenados (two-sum, three-sum, par más cercano) usa el recorrido desde ambos extremos. Los pasos de mezcla en merge sort y los merge joins en bases de datos son recorridos de dos punteros. El paso de partition de quicksort y el particionado de la bandera holandesa son de dos punteros. Los rate limiters y los contadores de ventana deslizante en sistemas distribuidos usan la idea de ventana fija. Los problemas de deduplicación y run-length, y buena parte de la programación competitiva y las entrevistas técnicas, se apoyan en estos patrones. Donde sea que un cálculo sobre rangos contiguos o pares ordenados se pueda mantener incrementalmente, un barrido de dos punteros es probablemente la respuesta eficiente.

Puntos clave

Las técnicas de dos punteros y ventana deslizante convierten recorridos anidados O(n²) en pasadas únicas O(n) moviendo dos índices por los datos y manteniendo el estado de la ventana de forma incremental — una ventana variable que crece por la derecha y se encoge por la izquierda para conservar un invariante, un recorrido de dos punteros que converge desde ambos extremos de datos ordenados, o una ventana fija que agrega-uno-quita-uno conforme se desliza. El tiempo lineal viene del movimiento monótono de los punteros (cada índice solo avanza, total ≤ 2n) más actualizaciones O(1) por deslizamiento que reutilizan el estado de la ventana anterior — la misma amortización detrás del rolling hash y de KMP. En el peor caso del substring único más largo hizo 400× menos trabajo que la fuerza bruta. La precondición es que la propiedad de la ventana sea monótona y mantenible incrementalmente; reconocer esa forma es la verdadera habilidad.

El nivel de paradigmas cierra con una aplicación más de un viejo conocido en un escenario nuevo. La búsqueda binaria sobre la respuesta (lo que sigue) aplica la búsqueda binaria no a un array ordenado sino al espacio de respuestas posibles de un problema de optimización — adivinando repetidamente una respuesta candidata y haciendo una pregunta de factibilidad de sí/no — convirtiendo "encuentra el valor óptimo" en "verifica si un valor funciona", y resolviendo una variedad sorprendente de problemas que a primera vista no se parecen en nada a una búsqueda.