¿Qué es la técnica de dos punteros?

Question

Accepted Answer

La técnica de **dos punteros** utiliza dos índices que se mueven a través de una secuencia para resolver problemas en un solo paso — convirtiendo muchas soluciones O(n²) de fuerza bruta en **O(n)**.

## La idea

Mantén dos punteros (a menudo en los extremos, o uno lento y uno rápido) y muévelos según una condición, reduciendo el trabajo sin volver a escanear.

## Ejemplo: emparejar suma a un objetivo en un array ordenado

```python
def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)       # found the pair
        elif s < target:
            lo += 1               # need a bigger sum
        else:
            hi -= 1               # need a smaller sum
    return None

two_sum_sorted([1, 3, 4, 6, 9], 10)   # -> (1, 3) for 4 + 6
```

## Complejidad

- **Tiempo:** O(n). **Espacio:** O(1).

## Cuándo usar / Trampas

Excelente para **arrays ordenados**, verificaciones de palíndromos, inversión y eliminación de duplicados en el lugar. El array generalmente debe estar ordenado para la variante de punteros convergentes. Ten cuidado con los límites de punteros y la condición del bucle (`lo < hi`).

## Por qué es importante

Dos punteros es uno de los patrones de entrevista de mayor apalancamiento: colapsa bucles anidados en un escaneo lineal limpio.

Te enseña a explotar la estructura (como la ordenación) en lugar de fuerza bruta.

La misma idea impulsa la fusión, la partición y el paso de fusión de merge sort.