O que é a técnica de dois ponteiros?

Question

Accepted Answer

A técnica de **dois ponteiros** usa dois índices que se movem através de uma sequência para resolver problemas em uma única passagem — transformando muitas soluções O(n²) de força bruta em **O(n)**.

## A ideia

Mantenha dois ponteiros (frequentemente nas extremidades, ou um lento e um rápido) e mova-os com base em uma condição, reduzindo o trabalho sem rescan.

## Exemplo: par que soma a um alvo em um 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
```

## Complexidade

- **Tempo:** O(n). **Espaço:** O(1).

## Quando usar / armadilhas

Ótimo para **arrays ordenados**, verificações de palíndromos, reversão e remoção de duplicatas no local. O array geralmente deve ser ordenado para a variante de ponteiros convergentes. Tenha cuidado com os limites de ponteiro e a condição de loop (`lo < hi`).

## Por que isso importa

Dois ponteiros é um dos padrões de entrevista com maior alavancagem: ele transforma loops aninhados em um scan linear limpo.

Ensina a explorar a estrutura (como a ordenação) em vez de força bruta.

A mesma ideia alimenta a mesclagem, o particionamento e a etapa de mesclagem da classificação por mesclagem.