Algoritmos Fundamentais: Busca por par ordenado

Tenho revisitado alguns livros que não abria há tempos e reaprendido a me divertir resolvendo problemas clássicos com algoritmos. Neste artigo, falo sobre um dos mais fundamentais: o problema dos dois ponteiros.

Busca por par ordenado

Um problema recorrente na engenharia de software é a busca por pares complementares em coleções de dados, por exemplo, encontrar dois valores que somam uma transferência ou identificar eventos duplicados dentro de uma janela de tempo.

Como em muitos problemas algorítmicos, existe a abordagem por força bruta e uma abordagem mais eficiente. Neste texto, exploro ambas e mostro quando cada uma faz sentido no mundo real.

Two Pointers

A solução ingênua (testar todas as combinações) tem custo O(n²) e rapidamente se torna inviável conforme o volume cresce.

O padrão Two Pointers resolve o mesmo problema em O(n), utilizando apenas duas variáveis.

O problema

Dado um array ordenado de números, encontre dois elementos cuja soma seja igual a um valor alvo.

Esse é o clássico Pair Sum, frequentemente usado como porta de entrada para o padrão Two Pointers. É comum em entrevistas técnicas (empresas como Google, Amazon e Nubank usam variações), mas sua utilidade vai muito além disso.

Exemplo:

Array: [1, 3, 5, 7, 9]
Alvo: 8
Resposta: índices (0, 3) → 1 + 7 = 8

A abordagem por força bruta

A primeira solução é comparar cada elemento com todos os outros:

for (int i = 0; i < numbers.length; i++) {
  for (int j = i + 1; j < numbers.length; j++) {
    if (numbers[i] + numbers[j] == target) {
      return new int[]{i, j};
    }
  }
}

Para 10.000 elementos, isso significa ~50 milhões de comparações. Sinere! Temos um problema.

Pensando melhor no problema

Se o array está ordenado, podemos explorar essa propriedade.

A ideia do Two Pointers é simples:

• Um ponteiro começa no início (menor valor)
• Outro no final (maior valor)

A soma dos dois determina o movimento:

• Soma < alvo → avança o ponteiro da esquerda
• Soma > alvo → recua o ponteiro da direita
• Soma == alvo → encontrou o par

Exemplo:

Array: [2, 4, 6, 8, 11]    Alvo: 10

left → 2     right → 11    soma = 13 > 10 → right--
left → 2     right → 8     soma = 10 ✓

Cada elemento é visitado no máximo uma vez.

Complexidade: O(n) tempo, O(1) espaço.

Implementação

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

  while (left < right) {
    int sum = numbers[left] + numbers[right];

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

  return new int[0];
}

Simples, previsível e eficiente.

Testes

Um algoritmo sem testes é apenas uma hipótese. Os cenários abaixo cobrem os casos de borda descritos no livro Coding Interview Patterns (Alex Xu & Sahn Lam), a referência que uso para estruturar esses estudos.

@Test
void sorted() {
  var pairSum = new PairSum();

  assertArrayEquals(new int[0], pairSum.sorted(new int[0], 0));
  assertArrayEquals(new int[0], pairSum.sorted(new int[]{1}, 1));
  assertArrayEquals(new int[]{0, 1}, pairSum.sorted(new int[]{2, 3}, 5));
  assertArrayEquals(new int[0], pairSum.sorted(new int[]{2, 4}, 5));

  var pair = pairSum.sorted(new int[]{2, 2, 3}, 5);
  assertTrue(
      Arrays.equals(new int[]{0, 2}, pair) ||
      Arrays.equals(new int[]{1, 2}, pair)
  );

  assertArrayEquals(new int[]{0, 2}, pairSum.sorted(new int[]{-1, 2, 3}, 2));
  assertArrayEquals(new int[]{0, 1}, pairSum.sorted(new int[]{-3, -2, -1}, -5));
}

Esses cenários cobrem:

• bordas (array vazio, elemento único)
• duplicados
• números negativos

Cada cenário testa uma fronteira diferente do algoritmo. Array vazio e elemento único validam as guardas de entrada.

Elementos duplicados garantem que o ponteiro não pula combinações válidas. Números negativos confirmam que a lógica de convergência funciona independentemente do sinal.

Para explorar mais cenários (como implementações em Python, C++ e JavaScript, ou variantes como 3Sum e 4Sum), o LeetCode é o ponto de partida clássico.

Casos reais de uso

Conciliação financeira

Sistemas financeiros precisam reconciliar lançamentos agregados com transações individuais.

Ordenando os valores, o Two Pointers encontra rapidamente combinações que explicam um lançamento consolidado, inclusive com tolerância para arredondamento.

E-commerce: “complete o valor”

Plataformas podem sugerir pares de produtos que fecham exatamente um orçamento ou atingem frete grátis.

Com catálogos grandes, O(n) faz diferença direta na experiência do usuário.

Portfólio de investimentos

Robo-advisors podem combinar dois ativos para atingir uma meta de retorno.

O problema se reduz a encontrar dois valores cuja soma atenda a restrição definida.

Quando usar (e quando não usar)

• Use Two Pointers quando os dados já estiverem ordenados
• Use HashMap quando não estiverem e você precisa de O(n)
• Ordenar + Two Pointers (O(n log n)) também pode ser uma boa estratégia dependendo do contexto

Conclusão

Two Pointers não é apenas um exercício de entrevista, é uma técnica prática e aplicável.

Ele substitui soluções quadráticas por lineares em problemas reais, com uma implementação simples e sem custo adicional de memória.

No fim, é um bom exemplo de como dominar fundamentos ainda é uma das melhores formas de lidar com complexidade, inclusive na era da IA.