Two Pointers

Uma técnica, não um algoritmo

Vale começar por uma distinção que muda o jeito de estudar o assunto. Um algoritmo é uma sequência definida de passos: o Bubble Sort é sempre o Bubble Sort, o Merge Sort é sempre o Merge Sort. Two Pointers não é isso, e também não é uma estrutura de dados, porque não diz nada sobre como os dados ficam organizados na memória. É uma técnica: um jeito de abordar o problema, que aparece com formatos bem diferentes dependendo do que você precisa responder.

A definição é curta: você mantém dois índices apontando para posições diferentes e move cada um segundo uma regra que depende do que está lendo. O ganho vem sempre da mesma coisa: a cada passo você elimina possibilidades sem precisar testá-las.

Os nomes variam (i e j, left e right, p1 e p2, lento e rapido), mas os formatos que aparecem na prática são poucos:

Existe ainda um terceiro caso, que confunde no começo: um ponteiro em cada entrada. Quando o problema traz dois arrays ou duas strings (verificar se uma é subsequência da outra, fazer o merge de duas listas ordenadas), cada estrutura ganha o seu índice. Continua sendo Two Pointers, mesmo com os dois começando na posição zero.

Por que quase sempre array e string? Porque as duas dão acesso aleatório: nums[i] custa O(1) e você pula de qualquer posição para qualquer outra. Numa lista simplesmente ligada não dá para colocar um ponteiro no fim e andar para trás, porque o nó não sabe quem veio antes dele. Só uma lista duplamente ligada permitiria isso. Por consequência, o sabor que sobra para listas encadeadas é o de mesma direção, com um ponteiro andando mais rápido que o outro.

O que custa testar todos os pares

O problema motivador é o clássico: dado um array ordenado e um alvo, existem dois números que somam o alvo?

A primeira solução que vem à cabeça testa todo mundo com todo mundo:

def dois_numeros_forca_bruta(nums, alvo):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == alvo:
                return [i, j]
    return []

Funciona, e é O(n²). O número exato de pares que esse código percorre no pior caso é n(n-1)/2:

Repare no que essa solução joga fora: ela sabe que o array está ordenado e não usa isso para nada. Testar nums[0] + nums[1] depois de já ter descoberto que nums[0] + nums[7] ficou pequeno demais é trabalho jogado no lixo, porque nums[1] é menor que nums[7] e a soma só pode ficar pior. É essa informação desperdiçada que o Two Pointers transforma em velocidade.

Convergentes: o Two Sum em array ordenado

A regra cabe em três linhas. Um ponteiro na primeira posição, outro na última, e olhe a soma:

• Soma maior que o alvo: o único jeito de diminuir é trocar o número grande por um menor, então recue a direita.
• Soma menor que o alvo: o único jeito de aumentar é trocar o número pequeno por um maior, então avance a esquerda.
• Soma igual ao alvo: achou, pode devolver.

Com o array [1, 2, 3, 6, 8, 10, 20, 21] e alvo 16, a busca inteira cabe em seis somas:

Seis somas contra os 28 pares da força bruta, no mesmo array. O código é quase a tabela escrita em Python:

def dois_ponteiros(nums, alvo):
    esquerda = 0
    direita = len(nums) - 1
    while esquerda < direita:
        soma = nums[esquerda] + nums[direita]
        if soma == alvo:
            return [esquerda, direita]
        if soma < alvo:
            esquerda += 1
        else:
            direita -= 1
    return []

Rode o visualizador passo a passo e acompanhe dois números do painel de baixo ao mesmo tempo: somas avaliadas e pares na força bruta. Com o preset "Alvo 16: os dois ponteiros andam" ele termina em 6 contra 28. Depois experimente:

• Acerta de cara: alvo 22. O par está exatamente nas duas pontas, então uma única soma resolve. É o melhor caso, O(1).
• Sem solução: alvo 100. Nenhum par existe e, mesmo assim, foram só 7 somas, ou seja n - 1. Esse é o pior caso da técnica: cada soma queima um índice de vez, e depois de n - 1 delas os ponteiros se encontram. A força bruta teria feito as 28 do mesmo jeito.
• Tudo igual: alvo 11. Tente prever antes de rodar. Com [5, 5, 5, 5] toda soma dá 10, nunca 11. O algoritmo não trava nem repete: avança a esquerda três vezes e encerra.
• Digite um array fora de ordem no campo de entrada. Ele é reordenado sozinho, de propósito, porque é exatamente o que você teria que fazer antes de aplicar a técnica. Sem ordem, o passo a passo não faz sentido nenhum.
• Sortear monta um array e um alvo novos, que às vezes nem têm solução. Use para treinar a previsão: antes de apertar Rodar, diga em voz alta quantas somas vão sair. Você vai errar por cima nas primeiras vezes, porque a intuição ainda está calibrada na força bruta.

Por que mover um ponteiro só não perde solução

Esta é a parte que separa quem decorou de quem entendeu. Mover um ponteiro por vez parece arriscado: e se a resposta estivesse justamente no par que você descartou sem testar?

Não estava, e o motivo é a ordenação. Chame de E e D os índices atuais.

• Se soma > alvo, então nums[D] é grande demais para qualquer parceiro à direita de E. Como nums[E] já é o menor valor ainda disponível, todo par formado com D só pode dar uma soma maior ou igual à atual. Logo o índice D está esgotado, e recuar a direita não perde nada.
• Se soma < alvo, o argumento é simétrico: nums[D] já é o maior valor disponível, então nums[E] não fecha com ninguém. O índice E está esgotado, e avançar a esquerda não perde nada.

Cada passo elimina uma linha ou uma coluna inteira da tabela de pares, e não um par só. É por isso que n - 1 somas bastam para cobrir os n(n-1)/2 pares possíveis.

Sobre o custo, dois pontos:

• Tempo O(n). Cada índice é visitado no máximo uma vez, e os dois ponteiros juntos percorrem o array inteiro. Como cada iteração move um dos dois, o laço roda no máximo n - 1 vezes. Na prática cada ponteiro anda metade do array, mas n/2 é O(n): a constante cai, como em qualquer conta de Big O.
• Espaço O(1). Não existe estrutura auxiliar, só duas variáveis inteiras. Sejam 10 elementos ou 1 milhão, o consumo extra é o mesmo.

Vale guardar a ressalva: a notação assintótica não conta tudo. Dois algoritmos O(n) podem ter constantes bem diferentes, e andar metade do array é, na vida real, duas vezes mais rápido que andar o array inteiro. O Big O classifica a curva, não cronometra o relógio.

O mesmo argumento sem soma nenhuma: Container With Most Water

O raciocínio acima não é sobre soma, é sobre conseguir provar que um índice está esgotado. Trocar a soma por outra função mantém a técnica de pé, e o Container With Most Water é o exemplo canônico disso.

O enunciado dá alturas de barras verticais e pergunta qual par delas segura mais água. A área entre E e D é:

area = min(altura[E], altura[D]) * (D - E)

A largura é a distância entre os índices e a altura é limitada pela barra menor, porque a água transborda por cima dela. E é justamente isso que dá a regra de movimento: mova sempre o ponteiro da barra menor.

A prova tem duas partes. Qualquer movimento diminui a largura, isso é inevitável, porque os ponteiros só andam para dentro. Então, para melhorar a área, é preciso ganhar altura. Se você mantiver a barra menor e mover a outra, a altura continua limitada pela mesma barra menor (ou piora), e a largura encolheu: a área só pode cair. Logo todo par que ainda envolve a barra menor está esgotado, e descartá-la não perde a resposta.

Com o array clássico [1, 8, 6, 2, 5, 4, 8, 3, 7], os dois ponteiros varrem tudo em 8 avaliações contra os 36 pares da força bruta, e a melhor área aparece logo na segunda:

Repare no passo 4: quando as duas alturas empatam, tanto faz qual você move. Nesse caso as duas barras estão esgotadas ao mesmo tempo, porque qualquer par futuro com uma delas tem largura menor e altura no máximo igual. Por isso if altura[esq] < altura[dir] e if altura[esq] <= altura[dir] dão a mesma resposta, e dá até para mover os dois de uma vez.

Palíndromo: dois ponteiros em ritmos diferentes

Palavra palíndroma é aquela que se lê igual de trás para frente. Com dois ponteiros convergentes, a verificação é imediata: compare as pontas, feche os dois ponteiros, repita.

• arara: a com a, depois r com r, os ponteiros se encontram no a do meio. É palíndromo, com 2 comparações.
• banana: b com a já na primeira comparação. Não é palíndromo, e o algoritmo para na primeira iteração, sem olhar o resto.
• Ana: A com a, ignorando maiúscula. Uma comparação e acabou.

Repare na condição do laço: esq < dir, com < estrito. Ela cobre os dois formatos de palavra sem nenhum if a mais. Numa palavra ímpar os ponteiros param no mesmo caractere, o do meio, e ele não precisa ser comparado porque é palíndromo de si mesmo. Numa palavra par eles se cruzam (esq fica um passo à frente de dir) e não sobra nada no meio. Trocar por <= só acrescentaria uma comparação de um caractere com ele mesmo, que é sempre verdadeira.

O problema fica interessante quando o enunciado manda ignorar espaço, pontuação e maiúscula, que é o caso do clássico "A man, a plan, a canal: Panama". A saída óbvia é limpar a string antes:

def e_palindromo_ingenuo(s):
    limpa = ""
    for c in s:
        if c.isalnum():
            limpa += c.lower()
    return limpa == limpa[::-1]

Correto e legível, mas com dois custos escondidos. Primeiro, string em Python é imutável: cada concatenação cria uma string nova, e limpa[::-1] cria mais uma. A memória extra vira O(n), justamente o que a técnica prometia evitar. Segundo, é por aí que a limpeza anda em círculos: você troca espaço, depois vírgula, depois dois pontos, e sempre falta um caractere novo.

A saída é não tocar na string. Se o caractere atual não interessa, pule só aquele ponteiro e deixe o outro parado. É aqui que está o insight principal: os dois ponteiros não precisam andar no mesmo ritmo.

def e_palindromo(s):
    esq, dir = 0, len(s) - 1
    while esq < dir:
        if not s[esq].isalnum():
            esq += 1
        elif not s[dir].isalnum():
            dir -= 1
        elif s[esq].lower() != s[dir].lower():
            return False
        else:
            esq += 1
            dir -= 1
    return True

O visualizador começa com a frase do Panamá, que tem 30 caracteres. Rode até o fim e compare os dois últimos cartões do painel: strings novas aqui = 0 contra strings novas limpando antes = 22. Esses 22 são as 21 concatenações do limpa += c.lower(), uma por caractere aproveitado, mais a cópia invertida do limpa[::-1]. É a diferença entre O(1) e O(n) de espaço, com número em cima da mesa. Confira também as 10 comparações e os 9 saltos: os saltos são exatamente os 9 caracteres que não são letra nem dígito (as vírgulas, os espaços e os dois pontos), e cada um deles move um ponteiro só, deixando o outro parado. Depois:

• Clique em banana (falha no passo 1) e repare que a nota fica vermelha logo no passo 2 da animação. Falhar cedo é uma vantagem: você não paga o custo do resto da entrada.
• Clique em race a car (falha no fim) para ver o contrário. Foram 4 comparações e 1 salto antes de descobrir que e não bate com a. Mesmo no pior caso a conta é n/2, não n².
• Clique em arara e conte as células: com 5 caracteres, só 2 comparações. Um palíndromo de n caracteres custa n/2 comparações, não n.
• Clique em vazio (caso de borda). A string vazia é palíndromo por vacuidade, e repare que o while nem chega a rodar, porque esq = 0 já não é menor que dir = -1. Nenhum if extra foi preciso: a condição do laço cuida do caso sozinha, e é isso que você quer conferir em toda solução de dois ponteiros antes de submeter.
• Antes de clicar em 0P, responda: "0P" é palíndromo? A resposta é não, 0 é diferente de p. Guarde isso, o próximo bloco explica por que essa entrada é famosa.

Mesma direção: o leitor e o escritor

No sabor convergente os ponteiros vêm das pontas. No sabor de mesma direção, os dois saem da esquerda e um anda mais rápido que o outro. O uso mais comum é a remoção in-place, onde eles ganham nomes melhores: leitor e escritor.

O leitor percorre o array inteiro, sem pular nada. O escritor só anda quando encontra algo que merece ficar. No fim, o prefixo até o escritor é a resposta, e nenhum array novo foi alocado.

def remove_duplicados(nums):
    if not nums:
        return 0
    escrita = 1
    for leitura in range(1, len(nums)):
        if nums[leitura] != nums[escrita - 1]:
            nums[escrita] = nums[leitura]
            escrita += 1
    return escrita

Com [0, 0, 1, 1, 1, 2, 2, 3, 3, 4], o leitor dá 9 passos, o escritor para em 5, e as cinco primeiras posições viram [0, 1, 2, 3, 4]. O resto do array continua com lixo, e é por isso que esse tipo de problema pede o tamanho de volta, não o array.

O mesmo formato resolve o caso das duas entradas, com um ponteiro em cada uma. Verificar se uma palavra é subsequência da outra, por exemplo:

def e_subsequencia(pequena, grande):
    i = j = 0
    while i < len(pequena) and j < len(grande):
        if pequena[i] == grande[j]:
            i += 1
        j += 1
    return i == len(pequena)

"ana" é subsequência de "banana": o ponteiro da esquerda anda quando bate a letra, o da direita anda sempre. E "ann" também é, porque subsequência não exige que as letras sejam vizinhas, só que a ordem seja respeitada. Já "ann" não é substring de "banana", porque substring é fatia contígua. Aqui as duas entradas têm tamanhos independentes, então a complexidade é O(n + m), e não O(n).

Rápido e lento: o ciclo da lista ligada

Numa lista simplesmente ligada você não consegue colocar um ponteiro no fim, e nem sempre existe fim: se algum nó apontar para um nó anterior, percorrer a lista vira um laço infinito. Descobrir isso gastando memória é fácil, basta um conjunto com os nós já visitados, mas isso custa O(n) de espaço. A versão com dois ponteiros custa O(1).

A ideia (conhecida como algoritmo da lebre e da tartaruga, ou Floyd) é soltar dois ponteiros do mesmo ponto de partida com velocidades diferentes: o lento anda 1 nó por iteração, o rápido anda 2.

def tem_ciclo(cabeca):
    lento = rapido = cabeca
    while rapido and rapido.prox:
        lento = lento.prox
        rapido = rapido.prox.prox
        if lento is rapido:
            return True
    return False

Se não existe ciclo, o rápido chega ao fim e o while termina. Se existe ciclo, os dois acabam presos nele, e aí vem o argumento bonito: dentro do ciclo, o rápido se aproxima do lento em exatamente 1 posição por iteração. Uma distância que diminui de 1 em 1 nunca pula por cima do zero, então o encontro é garantido, e acontece em no máximo tantas iterações quanto o número de nós.

O visualizador abre no caso clássico: 3 nós de cauda e um ciclo de 5. Rode até o fim e acompanhe o painel: são 5 iterações, o lento anda 5 nós, o rápido anda 10, e os dois se encontram no nó 5. Repare na iteração 4, quando o rápido "dá a volta" no ciclo e reaparece atrás do lento, no nó 3 contra o nó 4. Depois:

• Sem ciclo: 6 nós em fila. O rápido cai fora da lista e a resposta é não. Repare que bastaram 3 iterações para ele chegar ao fim de uma lista de 6 nós, enquanto o lento parou no nó 3: andar de dois em dois consome a lista na metade das iterações.
• Laço em si mesmo: 3 + ciclo de 1. O último nó aponta para ele mesmo. É o menor ciclo possível, e o algoritmo o pega em 3 iterações, sem tratamento especial nenhum.
• Só ciclo: 6 nós em roda. Sem cauda, a lista inteira é o ciclo. São 6 iterações, e não é coincidência: lista sem cauda é o único formato em que o encontro gasta exatamente o número de nós. Deixe a cauda em zero e varie só o tamanho do ciclo: o número de iterações vai bater com o tamanho do ciclo, sempre.
• Arraste os dois controles e tente prever o número de iterações antes de rodar. A regra exata é bonita: o encontro acontece no primeiro múltiplo do tamanho do ciclo que já é grande o bastante para o lento ter entrado no ciclo. Com cauda 3 e ciclo 5, o primeiro múltiplo de 5 que chega a 3 é o próprio 5, e dá 5 iterações. Com cauda 6 e ciclo 5, o primeiro múltiplo de 5 que chega a 6 é 10, e o encontro demora 10. Teste os dois no visualizador.

Duas consequências que valem para a entrevista. A primeira: aumentar a cauda não deixa a busca mais rápida, e pode deixar bem mais lenta (3 e 5 dão 5 iterações, 6 e 5 dão 10). A segunda: por maior que fique, o encontro nunca passa de cauda mais ciclo, ou seja, nunca passa do número de nós da lista. É esse teto que faz o algoritmo ser O(n) de tempo com O(1) de espaço, contra o O(n) e O(n) da solução com conjunto de visitados.

Ordenar para usar dois ponteiros: o trade-off com hash

Toda a construção acima depende de o array estar ordenado. E quando ele não está?

Aí você tem uma escolha. O Two Sum clássico (o de array desordenado) tem a solução com tabela hash: você percorre uma vez guardando o complemento de cada número, e responde em O(n). Rápido, mas gasta O(n) de memória.

A alternativa é ordenar e aplicar dois ponteiros:

A leitura da tabela é a parte que importa. Ordenar piora o tempo, porque nenhum algoritmo de ordenação por comparação faz melhor que O(n log n), e esse termo passa a dominar tudo o que vem depois. O que você compra em troca é memória constante. Se o problema, o entrevistador ou o ambiente de produção impuserem um limite de memória, esse é o caminho.

Duas ressalvas honestas sobre essa última linha. A primeira: o O(1) da terceira linha vale para o par de ponteiros, e supõe uma ordenação in-place. O nums.sort() do Python usa Timsort, que no pior caso pede O(n) de área temporária, então se a pergunta for exatamente "quanta memória extra", diga "O(1) além da ordenação" em vez de só "O(1)". A segunda: ordenar modifica a entrada. Se quem chamou a função ainda precisa do array original, você acabou de estragá-lo, e o sorted(nums) que resolve isso já custa O(n) de memória.

E tem a armadilha que só aparece quando você roda: o Two Sum original pede os índices originais dos dois números. Ordenar destrói exatamente essa informação, e o sintoma é sempre o mesmo: os valores encontrados estão certos, os índices devolvidos estão errados. Duas saídas honestas:

• Se o problema pede os valores (ou só um verdadeiro/falso), pode ordenar à vontade.
• Se o problema pede os índices, ordene uma lista de pares (valor, indice). Só que isso aloca uma cópia do array, o espaço volta a ser O(n), e aí o hash costuma ser melhor mesmo.

3Sum: fixar um número e resolver um Two Sum no resto

O 3Sum é onde tudo isto se junta, e é o problema em que a maioria das pessoas trava. Pede as triplas únicas que somam zero, num array desordenado. A força bruta de três laços é O(n³), inviável já com alguns milhares de elementos.

A construção sai de uma pergunta só: se eu fixar o primeiro número da tripla, o que sobra? Sobra "achar dois números que somam -nums[i]", que é exatamente o Two Sum convergente que você já sabe fazer. Como três laços viram um laço externo mais uma varredura de dois ponteiros, o custo cai para O(n²).

def tres_somas(nums):
    nums.sort()                       # O(n log n), e é o que habilita tudo
    n = len(nums)
    resultado = []
    for i in range(n - 2):
        if nums[i] > 0:               # ordenado: daqui para frente só cresce
            break
        if i > 0 and nums[i] == nums[i - 1]:
            continue                  # já resolvi este valor como fixo
        esq, dir = i + 1, n - 1
        while esq < dir:
            soma = nums[i] + nums[esq] + nums[dir]
            if soma < 0:
                esq += 1
            elif soma > 0:
                dir -= 1
            else:
                resultado.append([nums[i], nums[esq], nums[dir]])
                while esq < dir and nums[esq] == nums[esq + 1]:
                    esq += 1
                while esq < dir and nums[dir] == nums[dir - 1]:
                    dir -= 1
                esq += 1
                dir -= 1
    return resultado

São quatro decisões, e cada uma resolve um problema específico:

Com [-1, 0, 1, 2, -1, -4], o array ordenado vira [-4, -1, -1, 0, 1, 2] e a resposta é [[-1, -1, 2], [-1, 0, 1]]. Repare que a tripla [-1, -1, 2] usa os dois -1, e mesmo assim ela aparece uma vez só: o continue do laço externo pula o segundo -1 como fixo, mas nada impede que ele seja usado como parceiro lá dentro. Confundir essas duas coisas é o bug mais comum do 3Sum.

Onde o Two Pointers dá errado

Esquecer que precisa estar ordenado. É o erro número um. Se a solução depende de "a soma está grande demais, recuo a direita", ela depende de ordem. Sem ordem, o resultado fica errado sem dar exceção, que é o pior tipo de bug.

Confundir esquerda < direita com esquerda <= direita. Para formar um par de índices distintos, use <, senão o elemento do meio soma com ele mesmo e [3, 8] com alvo 6 devolve um par que não existe. Para palíndromo também é <, porque o caractere central não precisa de comparação. O <= aparece em outro contexto, o da busca binária, onde o intervalo pode ter um elemento só.

Mover os dois ponteiros quando só um devia andar. É o erro do palíndromo com pontuação. Se um lado tem um caractere para ignorar, quem anda é ele, sozinho. Fechar os dois de uma vez desalinha a comparação e passa pelos testes fáceis, quebrando só nos difíceis.

Errar a inicialização da direita. direita = len(nums) estoura o índice na primeira leitura. É sempre len(nums) - 1, e esse é literalmente o primeiro erro que aparece quando se escreve o laço.

Esquecer os duplicados no 3Sum. Quando o problema pede triplas ou pares únicos, o array ordenado coloca os valores repetidos lado a lado, e o laço vai gerar a mesma resposta várias vezes. A correção é pular os valores iguais ao anterior depois de registrar uma solução.

Chamar de Two Pointers o que tem nome próprio. Se a distância entre os ponteiros define uma janela cujo conteúdo interessa, isso é Sliding Window. Se um anda o dobro do outro, é lento e rápido. Reconhecer o nome certo é parte da resposta.

Os casos de borda que derrubam a submissão

Quase toda solução de dois ponteiros que passa nos exemplos e falha no LeetCode falha em um destes seis. Rode-os de cabeça antes de submeter:

Nas variações de lista ligada, a lista tem três bordas próprias: vazia (cabeca is None, o while rapido and rapido.prox já devolve falso), um nó sem ciclo (rapido.prox é None na primeira checagem) e um nó apontando para si mesmo (encontro na primeira iteração). Nenhuma delas precisa de if extra: quem escreveu a condição do while certa ganha as três de graça, e é por isso que a ordem rapido and rapido.prox importa. Invertida, ela estoura com None.

Como praticar

Antes da lista, guarde o gatilho de cada sabor. Na entrevista você tem uns segundos para escolher, e a escolha vem do enunciado, não da inspiração:

O esqueleto convergente cabe na memória, e é dele que saem quatro dos seis problemas abaixo. Decore a forma, não o problema:

esq, dir = 0, len(dados) - 1
while esq < dir:
    valor = metrica(dados[esq], dados[dir])   # soma, área, comparação...
    if resolve(valor):
        return resposta(esq, dir)
    if precisa_de_mais(valor):
        esq += 1        # descarta o índice esq, ele não fecha com ninguém
    else:
        dir -= 1        # descarta o índice dir, pelo mesmo motivo
return nao_achou

A única coisa que muda de problema para problema são as três funções do meio. Se você não conseguir escrever, em uma frase, por que o índice descartado está esgotado, ainda não é hora de codar: é aí que nascem as soluções que passam nos exemplos e falham nos testes escondidos.

Feito isso, siga a ordem da lista de problemas abaixo, que vai do formato mais direto ao mais elaborado. O caminho é este:

1. Valid Palindrome é a versão exata do que você viu no visualizador do meio, pontuação e tudo. Resolva primeiro limpando a string e depois sem criar string nenhuma, e compare a memória que o LeetCode reporta nas duas.
2. Remove Duplicates treina o leitor e o escritor. Se você conseguir dizer, sem rodar, o que sobra no array depois do índice devolvido, entendeu o padrão.
3. Linked List Cycle é o lento e rápido puro. Teste antes os casos de borda: lista vazia, um nó só, e um nó apontando para ele mesmo.
4. Two Sum II é o convergente clássico. Atenção: esse enunciado usa índices começando em 1, então some 1 na resposta.
5. Container With Most Water é o convergente sem soma nenhuma, e com entrada desordenada. Antes de olhar o código da seção sobre o argumento de descarte, tente reconstruir sozinho por que mover a barra menor é a escolha certa. Meta: 8 avaliações no array de exemplo.
6. 3Sum junta tudo: ordenar, fixar um elemento e resolver um Two Sum com dois ponteiros no resto, cuidando dos duplicados. Se travar, volte ao esqueleto da seção sobre o trade-off com hash e refaça linha a linha, explicando em voz alta por que cada continue existe.

Antes de cada problema, faça o exercício de prever: quantas comparações a força bruta faria, e quantas os dois ponteiros fazem? Se a diferença for grande, você está no problema certo.

Daqui, os vizinhos naturais são a Sliding Window, que é o mesmo par de ponteiros com uma regra de janela, e as tabelas hash, que resolvem em O(n) o que aqui custou uma ordenação. Se a conta de complexidade ainda escorrega, vale revisitar o Big O.

Vídeo da aula

Direto do canal da comunidade Craft & Code Club · 1:11:13.

▶

Problemas para praticar

Na ordem em que recomendamos resolver. Marque os que você já fez, fica salvo aqui.

Referências

Artigos e materiais externos para se aprofundar.