Two Pointers e Sliding Window: Técnicas para otimizar arrays e strings

1. Visão geral

Quando você encontra problemas de percurso de array ou string onde a solução brute-force executa em O(n²) ou O(n³), as técnicas two pointers e sliding window geralmente ajudam você a reduzir a complexidade para O(n). Este artigo explica a ideia central de cada técnica, com exemplos específicos em Java: two sum em array ordenado, verificação de palindromo, soma máxima de um subarray de tamanho fixo, e substring mais longa sem caracteres repetidos. Após ler, você reconhecerá o padrão e conseguirá aplicá-lo a muitos problemas semelhantes.

2. O que é Two Pointers

Two pointers é uma técnica que usa duas variáveis de índice (ponteiros) se movendo sobre uma estrutura de dados (geralmente um array ou string ordenada) para evitar percurso aninhado. Os dois ponteiros podem se mover:

• Na mesma direção (fast/slow): usado para remover elementos duplicados, detectar ciclos.
• Em direção oposta (left/right das duas extremidades): usado para encontrar pares com soma igual a alvo, verificar palíndromos.

2.1. Two pointers em direção oposta: encontrar um par com soma igual ao alvo

Problema clássico: dado um array ordenado em ordem crescente, encontre dois números cuja soma seja igual ao alvo.

public class TwoSumSorted {

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

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

Explicação:

• left começa do início do array, right do final do array.
• Se sum < target, o número em left é muito pequeno, então incremente left para obter um número maior.
• Se sum > target, o número em right é muito grande, então decremente right.
• O loop é executado em no máximo n passos porque cada vez que left ou right se move uma posição, resultando em complexidade O(n) em vez de O(n²) da abordagem de iteração aninhada.

Teste com JUnit 5 + AssertJ:

<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>5.10.2</version>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.assertj</groupId>
    <artifactId>assertj-core</artifactId>
    <version>3.25.3</version>
    <scope>test</scope>
</dependency>

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class TwoSumSortedTest {

    private final TwoSumSorted twoSum = new TwoSumSorted();

    @Test
    void shouldFindPairWhenSumMatchesTarget() {
        int[] numbers = {1, 3, 5, 8, 11};

        int[] result = twoSum.findPair(numbers, 13);

        assertThat(result).containsExactly(5, 8);
    }
}

Nota: esta técnica requer o array ordenado. Se o array não estiver ordenado, você deve ordenar primeiro (O(n log n)) ou usar HashMap para manter O(n) sem ordenação.

2.2. Two pointers para verificação de palindromo

public class PalindromeChecker {

    public boolean isPalindrome(String text) {
        int left = 0;
        int right = text.length() - 1;

        while (left < right) {
            if (text.charAt(left) != text.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

Os dois ponteiros começam das duas extremidades da string, comparam caracteres e depois se movem para dentro. Se um par de caracteres diferentes é encontrado, retorne false imediatamente — não é necessário percorrer toda a string. É por isso que essa técnica é mais rápida do que reverter a string e comparar (reverse().equals()), porque evita criar objetos StringBuilder intermediários.

3. O que é Sliding Window

Sliding window é uma variação de two pointers, aplicada a problemas envolvendo subsequências contíguas (subarray/substring). Em vez de recalcular do início para cada posição de início, você mantém uma “janela” [left, right] e atualiza gradualmente conforme a janela desliza, reutilizando resultados previamente calculados.

Existem dois tipos:

• Janela de tamanho fixo: o tamanho da janela é fixo (por exemplo, k elementos).
• Janela de tamanho variável: o tamanho da janela se expande/contrai com base nas condições do problema.

3.1. Janela de tamanho fixo: soma máxima de subarray de tamanho k

public class MaxSumSubarray {

    public int maxSum(int[] numbers, int windowSize) {
        int windowSum = 0;
        for (int i = 0; i < windowSize; i++) {
            windowSum += numbers[i];
        }

        int maxSum = windowSum;
        for (int right = windowSize; right < numbers.length; right++) {
            windowSum += numbers[right] - numbers[right - windowSize];
            maxSum = Math.max(maxSum, windowSum);
        }
        return maxSum;
    }
}

Explicação:

• O primeiro loop calcula a soma da primeira janela (do índice 0 a windowSize - 1).
• A partir daí, cada vez que você desliza a janela um passo para a direita: adicione o novo elemento (numbers[right]), subtraia o elemento saindo da janela (numbers[right - windowSize]).
• Dessa forma, cada etapa custa apenas O(1) em vez de recalcular a soma O(k), resultando em complexidade total O(n).

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class MaxSumSubarrayTest {

    private final MaxSumSubarray solver = new MaxSumSubarray();

    @Test
    void shouldReturnMaxSumOfWindowSizeThree() {
        int[] numbers = {2, 1, 5, 1, 3, 2};

        int result = solver.maxSum(numbers, 3);

        assertThat(result).isEqualTo(9); // janela [5, 1, 3]
    }
}

3.2. Janela de tamanho variável: substring mais longa sem caracteres repetidos

Neste caso, a janela se expande/contrai com base na condição “sem caracteres repetidos”.

import java.util.HashMap;
import java.util.Map;

public class LongestUniqueSubstring {

    public int lengthOfLongestSubstring(String text) {
        Map<Character, Integer> lastSeenIndex = new HashMap<>();
        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < text.length(); right++) {
            char current = text.charAt(right);
            if (lastSeenIndex.containsKey(current) && lastSeenIndex.get(current) >= left) {
                left = lastSeenIndex.get(current) + 1;
            }
            lastSeenIndex.put(current, right);
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}

Explicação:

• right sempre avança (expandindo a janela), left apenas pula quando encontra um caractere duplicado dentro da janela atual.
• lastSeenIndex armazena a posição mais recente de cada caractere para saber para onde left deve pular.
• A condição lastSeenIndex.get(current) >= left garante que consideremos apenas como “duplicado” se esse caractere ainda estiver dentro da janela atual, evitando mover left para trás incorretamente.
• Cada caractere é processado exatamente uma vez em right, então a complexidade total é O(n).

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class LongestUniqueSubstringTest {

    private final LongestUniqueSubstring solver = new LongestUniqueSubstring();

    @Test
    void shouldReturnLengthOfLongestUniqueSubstring() {
        int result = solver.lengthOfLongestSubstring("abcabcbb");

        assertThat(result).isEqualTo(3); // "abc"
    }

    @Test
    void shouldHandleAllSameCharacters() {
        int result = solver.lengthOfLongestSubstring("bbbbb");

        assertThat(result).isEqualTo(1);
    }
}

Saída de debug manual com "abcabcbb":

right=0 'a' -> window="a"    length=1
right=1 'b' -> window="ab"   length=2
right=2 'c' -> window="abc"  length=3
right=3 'a' -> duplicado, left=1 -> window="bca" length=3
right=4 'b' -> duplicado, left=2 -> window="cab" length=3
...
maxLength = 3

4. Comparação e quando usar cada técnica

Situação	Técnica apropriada
Array ordenado, encontrar pares/triplos que satisfazem condição de soma	Two pointers em direção oposta
Verificação de simetria (palindromo), inverter array in-place	Two pointers em direção oposta
Remover elementos duplicados em array ordenado	Two pointers na mesma direção (fast/slow)
Subarray/substring com tamanho fixo k	Sliding window de tamanho fixo
Subarray/substring que satisfaz condição dinâmica (sem repetição, soma ≤ alvo…)	Sliding window de tamanho variável

Ponto em comum: ambas as técnicas evitam recalcular partes já processadas, convertendo de O(n²) para O(n) mantendo estado (sum, set, map) conforme os ponteiros/janelas se movem.

5. Erros comuns

• Esquecer a condição de parada left < right: pode facilmente causar loops infinitos ou comparar um elemento consigo mesmo quando left == right.
• Aplicar two pointers em arrays não ordenados sem ordenar primeiro — resultados completamente errados porque a lógica de incremento/decremento do ponteiro depende da monotonicidade do array.
• Em sliding window, esquecer de atualizar o estado quando left se desloca: por exemplo, esquecer de remover o elemento antigo de HashMap/sum, causando a janela “lembrar” dados que não fazem mais parte dela.
• Confundir as condições de expansão/contração da janela: com janelas de tamanho variável, você precisa identificar claramente qual condição faz right avançar, qual faz left avançar — se invertido, a janela nunca se contrairá corretamente.

Nota: essas duas técnicas não são adequadas quando o problema requer considerar todas as combinações não-contíguas (por exemplo, subset sum) — nesse caso, você precisa de backtracking ou programação dinâmica, não sliding window.

6. Conclusão

Two pointers e sliding window são duas ferramentas fundamentais para resolver problemas de array/string com complexidade linear. Reconhecer o padrão — array ordenado precisando encontrar pares, ou subarray/substring contíguo precisando de otimização — ajuda você a escolher a técnica correta e escrever código conciso, facilmente testável, como os exemplos acima. Durante a prática, tente traçar manualmente o estado de left/right através de cada etapa para entender claramente o invariante antes de codificar.