Problemas de maratona premiam quem reconhece um formato rápido. Dois ponteiros é o primeiro formato que vale aprender, porque não custa nada: nenhum segundo array, nenhum dicionário, nenhuma recursão. Duas variáveis int e o array que te deram.
Esta é a parte 1 de dez, cinco padrões cada. Todo programa abaixo é completo, rodou no .NET 10, e a saída dele está colada da execução.
Como rodar isto
O .NET 10 roda um único arquivo .cs sem projeto, sem classe e sem Main:
dotnet run twopointers.csIsso é novo, e é o jeito mais rápido de experimentar qualquer coisa disto. Tudo nesta página está escrito assim.
Padrão 1 — Fechando o cerco pelas duas pontas
Você tem um array ordenado. Encontre dois valores que somam um alvo.
A versão óbvia testa todos os pares. Num array de seis elementos, tudo bem. Conte o que ela faz de verdade:
int[] a = [2, 7, 11, 15, 19, 26];
int target = 30;
int bruteSteps = 0;
for (int i = 0; i < a.Length; i++)
for (int j = i + 1; j < a.Length; j++)
{
bruteSteps++;
if (a[i] + a[j] == target) goto done;
}
done:
int twoPtrSteps = 0;
int lo = 0, hi = a.Length - 1;
while (lo < hi)
{
twoPtrSteps++;
int sum = a[lo] + a[hi];
if (sum == target) break;
if (sum < target) lo++; else hi--;
}
Console.WriteLine($"n = {a.Length}");
Console.WriteLine($"every pair : {bruteSteps} pairs examined");
Console.WriteLine($"two pointers : {twoPtrSteps} steps");Ele imprime:
n = 6
every pair : 11 pairs examined
two pointers : 4 stepsOnze pares contra quatro passos não é uma diferença interessante. Com n = 100000 são cinco bilhões contra cem mil, e isso é a maratona inteira.
A jogada é esta. O array está ordenado, então a[hi] é o maior valor ainda em jogo. Se a[lo] + a[hi] é pequeno demais, então a[lo] não tem par em lugar nenhum — você acabou de juntá-lo com a maior coisa disponível e mesmo assim ficou curto. Então a[lo] não pode fazer parte de nenhuma resposta. Jogue fora e nunca mais olhe para ele.
A mesma lógica espelhada: se a soma é grande demais, a[hi] é grande demais para tudo que sobrou, então descarte.
Dois ponteiros fechando o cerco pelas duas pontas de um array ordenado. Uma célula cinza foi descartada e não é olhada de novo.
int[] a = [2, 7, 11, 15, 19, 26];
int target = 30;
int lo = 0, hi = a.Length - 1;
while (lo < hi)
{
int sum = a[lo] + a[hi];
string move = sum == target ? "= target, stop"
: sum < target ? "< target, lo++"
: "> target, hi--";
Console.WriteLine($"lo={lo} hi={hi} {a[lo],2} + {a[hi],2} = {sum,2} {move}");
if (sum == target) break;
if (sum < target) lo++; else hi--;
}
Console.WriteLine($"\nindices ({lo}, {hi}) -> values ({a[lo]}, {a[hi]})");Ele imprime:
lo=0 hi=5 2 + 26 = 28 < target, lo++
lo=1 hi=5 7 + 26 = 33 > target, hi--
lo=1 hi=4 7 + 19 = 26 < target, lo++
lo=2 hi=4 11 + 19 = 30 = target, stop
indices (2, 4) -> values (11, 19)Cada passo joga fora exatamente um índice e nunca o reconsidera. Existem n índices, então existem no máximo n passos. É por isso que é linear, e vale dizer dessa forma em vez de “os ponteiros se encontram no meio” — o descarte é o motivo, o encontro é só a aparência.
Custo: tempo O(n) depois da ordenação, espaço O(1).
Use quando a entrada estiver ordenada ou você puder pagar para ordená-la, e mover lo para a direita aumentar sua quantidade enquanto mover hi para a esquerda a diminui. Essa monotonicidade é o requisito inteiro. Sem ela o passo de descarte é inválido e a coisa toda devolve respostas erradas em silêncio.
Padrão 2 — O ponteiro de escrita
Remova as duplicatas de um array ordenado in-place, e informe quantos valores sobraram.
A versão tentadora monta uma List<int>, adiciona os que ficam, e copia de volta. Está correta. Também aloca um segundo array, e com 10⁶ elementos essa alocação é a diferença entre passar e não passar.
Aqui os dois ponteiros andam no mesmo sentido. r lê cada célula. w marca onde vai o próximo valor mantido. Nada é destruído porque w nunca consegue ultrapassar r — w só avança quando r avança, e começa atrás.
Um array, duas tarefas. r lê cada célula, w marca onde vai o próximo valor mantido. w nunca ultrapassa r, então nada é sobrescrito antes de ser lido. Tudo depois de w no final está velho e é ignorado.
int[] a = [1, 1, 2, 2, 2, 3, 4, 4, 5];
Console.WriteLine($"before: [{string.Join(", ", a)}]\n");
int w = 1;
for (int r = 1; r < a.Length; r++)
{
if (a[r] == a[w - 1])
{
Console.WriteLine($"r={r} a[r]={a[r]} {$"same as a[{w - 1}]",-12} skip w stays {w}");
continue;
}
a[w] = a[r];
w++;
Console.WriteLine($"r={r} a[r]={a[r]} {"new value",-12} a[{w - 1}]={a[r]} w -> {w}");
}
Console.WriteLine($"\nkept {w}: [{string.Join(", ", a[..w])}]");
Console.WriteLine($"tail : [{string.Join(", ", a[w..])}] <- stale, and that is fine");Ele imprime:
before: [1, 1, 2, 2, 2, 3, 4, 4, 5]
r=1 a[r]=1 same as a[0] skip w stays 1
r=2 a[r]=2 new value a[1]=2 w -> 2
r=3 a[r]=2 same as a[1] skip w stays 2
r=4 a[r]=2 same as a[1] skip w stays 2
r=5 a[r]=3 new value a[2]=3 w -> 3
r=6 a[r]=4 new value a[3]=4 w -> 4
r=7 a[r]=4 same as a[3] skip w stays 4
r=8 a[r]=5 new value a[4]=5 w -> 5
kept 5: [1, 2, 3, 4, 5]
tail : [3, 4, 4, 5] <- stale, and that is fineOlhe a cauda. [3, 4, 4, 5] fica lá parado, velho. Isso não é um bug para limpar — sobrescrever custaria outra passada sem benefício nenhum. O contrato é que a resposta é a[..w], e tudo depois de w não é da conta de quem chamou.
Custo: tempo O(n), espaço O(1).
Use quando o problema disser in place, ou devolva o novo tamanho, ou sem alocar. Compactar, filtrar e particionar por um predicado são todos este mesmo padrão vestindo outras palavras.
Padrão 3 — Ordene, ancore, varra
Encontre toda tripla que soma zero, sem reportar nenhuma tripla duas vezes.
Três laços aninhados é O(n³) e não vai passar. Mas fixe o primeiro valor e olhe o que sobra: encontrar dois valores que somam -a[i]. Isso é o padrão 1, exatamente. Ordenar uma vez no começo custa O(n log n) e compra a monotonicidade de que o padrão 1 precisa.
A parte genuinamente chata não é a busca, são as duplicatas. Elas precisam ser puladas em dois lugares diferentes, por dois motivos diferentes:
- Uma âncora repetida. Se
a[i] == a[i-1], toda tripla começando emijá foi encontrada começando emi-1. Pule a âncora inteira. - Um
loouhirepetido depois de um acerto. Depois de registrar uma tripla, ande com os dois ponteiros para além de qualquer cópia dos valores recém-usados, ou a iteração seguinte reporta a mesma tripla de novo.
Ordene uma vez, fixe um valor e rode dois ponteiros no que sobra. Pular uma âncora repetida é o que impede a mesma tripla de ser reportada duas vezes.
int[] a = [-1, 2, -4, -1, 1, 0];
Array.Sort(a);
Console.WriteLine($"sorted: [{string.Join(", ", a)}]\n");
List<(int, int, int)> found = [];
for (int i = 0; i < a.Length - 2; i++)
{
if (i > 0 && a[i] == a[i - 1])
{
Console.WriteLine($"anchor i={i} a[i]={a[i],2} duplicate anchor, skip");
continue;
}
int lo = i + 1, hi = a.Length - 1;
Console.WriteLine($"anchor i={i} a[i]={a[i],2} need a[lo] + a[hi] == {-a[i]}");
while (lo < hi)
{
int sum = a[i] + a[lo] + a[hi];
Console.WriteLine($" lo={lo} hi={hi} {a[i],2} + {a[lo],2} + {a[hi],2} = {sum,2}");
if (sum == 0)
{
found.Add((a[i], a[lo], a[hi]));
while (lo < hi && a[lo] == a[lo + 1]) lo++;
while (lo < hi && a[hi] == a[hi - 1]) hi--;
lo++; hi--;
}
else if (sum < 0) lo++;
else hi--;
}
}
Console.WriteLine();
foreach (var t in found) Console.WriteLine($"triplet: {t}");Ele imprime:
sorted: [-4, -1, -1, 0, 1, 2]
anchor i=0 a[i]=-4 need a[lo] + a[hi] == 4
lo=1 hi=5 -4 + -1 + 2 = -3
lo=2 hi=5 -4 + -1 + 2 = -3
lo=3 hi=5 -4 + 0 + 2 = -2
lo=4 hi=5 -4 + 1 + 2 = -1
anchor i=1 a[i]=-1 need a[lo] + a[hi] == 1
lo=2 hi=5 -1 + -1 + 2 = 0
lo=3 hi=4 -1 + 0 + 1 = 0
anchor i=2 a[i]=-1 duplicate anchor, skip
anchor i=3 a[i]= 0 need a[lo] + a[hi] == 0
lo=4 hi=5 0 + 1 + 2 = 3
triplet: (-1, -1, 2)
triplet: (-1, 0, 1)A âncora em i=2 é pulada sem um único passo interno, porque -1 já teve a vez dele em i=1. Esse pulo é o que faz a saída ser um conjunto em vez de uma lista com repetições.
Custo: tempo O(n²) — n âncoras, cada uma rodando uma varredura linear — mais a ordenação. Espaço O(1) além da saída.
Use quando você precisar de uma combinação de tamanho fixo que satisfaça uma condição. O four-sum é isto de novo com mais um laço por fora.
Padrão 4 — Mande cada valor para o índice dele
Um array guarda n valores no intervalo 1..n. Um valor aparece duas vezes, um está faltando. Encontre os dois, sem usar memória extra.
Um HashSet<int> resolve e custa memória O(n). O truque da soma dos valores te dá uma equação e você precisa de duas. Mas olhe a restrição de novo: os valores são 1..n e o array tem tamanho n. O array é uma hash table, e a função de hash é v - 1.
Então coloque cada valor onde ele pertence. O valor 3 vai para o índice 2. Se dois valores querem a mesma casa, o array para de conseguir se mexer, e a célula que nunca foi preenchida te diz o que está faltando.
O laço é um while, não um for, e isso importa. Depois de uma troca, o índice i guarda um valor diferente que ainda não foi colocado, então i não pode avançar. Ele avança só quando o valor em i está em casa.
A ordenação cíclica manda cada valor para o índice a que ele pertence. Quando dois valores querem a mesma casa o array para de se mexer, e o que sobra fora do lugar revela o duplicado e o número que falta.
int[] a = [3, 1, 5, 4, 3, 2];
Console.WriteLine($"start: [{string.Join(", ", a)}] values are 1..{a.Length}\n");
int i = 0;
while (i < a.Length)
{
int home = a[i] - 1;
if (a[i] != a[home])
{
Console.WriteLine($"i={i} a[i]={a[i]} belongs at index {home}, which holds {a[home]} swap");
(a[i], a[home]) = (a[home], a[i]);
Console.WriteLine($" -> [{string.Join(", ", a)}]");
}
else
{
Console.WriteLine($"i={i} a[i]={a[i]} is already home (or its twin is) i++");
i++;
}
}
Console.WriteLine($"\nsorted as far as it can be: [{string.Join(", ", a)}]\n");
for (int j = 0; j < a.Length; j++)
if (a[j] != j + 1)
Console.WriteLine($"index {j} holds {a[j]}, should hold {j + 1} -> duplicate = {a[j]}, missing = {j + 1}");Ele imprime:
start: [3, 1, 5, 4, 3, 2] values are 1..6
i=0 a[i]=3 belongs at index 2, which holds 5 swap
-> [5, 1, 3, 4, 3, 2]
i=0 a[i]=5 belongs at index 4, which holds 3 swap
-> [3, 1, 3, 4, 5, 2]
i=0 a[i]=3 is already home (or its twin is) i++
i=1 a[i]=1 belongs at index 0, which holds 3 swap
-> [1, 3, 3, 4, 5, 2]
i=1 a[i]=3 is already home (or its twin is) i++
i=2 a[i]=3 is already home (or its twin is) i++
i=3 a[i]=4 is already home (or its twin is) i++
i=4 a[i]=5 is already home (or its twin is) i++
i=5 a[i]=2 belongs at index 1, which holds 3 swap
-> [1, 2, 3, 4, 5, 3]
i=5 a[i]=3 is already home (or its twin is) i++
sorted as far as it can be: [1, 2, 3, 4, 5, 3]
index 5 holds 3, should hold 6 -> duplicate = 3, missing = 6Parece que poderia ser quadrático — um laço com uma troca dentro que às vezes não avança. Não é. Toda troca coloca pelo menos um valor na casa definitiva dele, e um valor que está em casa nunca é movido de novo. Existem n valores, então existem no máximo n trocas na execução inteira.
Quando os valores são uma permutação de um intervalo conhecido, o array já é uma hash table e você tem permissão para usá-lo como uma.
Custo: tempo O(n), espaço O(1).
Use quando o problema disser valores de 1 a n, ou de 0 a n, e pedir um que falta ou um duplicado. Essa frase é a pista, e ela está te fazendo um favor por estar ali.
Padrão 5 — Três regiões em uma passada
Ordene um array que contém só 0, 1 e 2. Uma passada, sem ordenação por comparação.
Contar cada valor e reescrever funciona, e são duas passadas. Também não generaliza, que é a objeção de verdade — a versão abaixo é como você particiona em torno de um pivô quando há muitas chaves iguais, que é o que impede o quicksort de degradar numa entrada cheia de duplicatas.
Três índices dividem o array em quatro regiões. Tudo à esquerda de low é um 0 resolvido. Tudo à direita de high é um 2 resolvido. Entre mid e high está a parte que ninguém olhou ainda, e ela encolhe em um a cada iteração.
O algoritmo inteiro são essas três regras mais uma invariante: tudo à esquerda de low é um 0, tudo à direita de high é um 2, e a região desconhecida encolhe em um a cada iteração. Essa última regra é a que as pessoas escrevem errado — o valor que volta na troca com high nunca foi examinado, então mid não pode passar por cima dele.
Leia a terceira regra de novo, porque é a que sai escrita errada. Quando você troca a[mid] com a[high], o valor que chega em mid veio da região não examinada. Ninguém testou ele. Avance mid por cima dele e você acabou de empurrar um valor não testado para dentro dos 1 resolvidos. Avançar mid no caso 0 está certo pelo motivo oposto: o valor que chega veio de low, e tudo antes de mid já foi testado.
int[] a = [2, 0, 2, 1, 1, 0, 2, 1, 0];
Console.WriteLine($"start: [{string.Join(", ", a)}]\n");
int low = 0, mid = 0, high = a.Length - 1;
while (mid <= high)
{
switch (a[mid])
{
case 0:
(a[low], a[mid]) = (a[mid], a[low]);
Console.WriteLine($"a[mid]=0 swap into the 0s low {low}->{low + 1} mid {mid}->{mid + 1} high {high} [{string.Join(", ", a)}]");
low++; mid++;
break;
case 1:
Console.WriteLine($"a[mid]=1 already correct low {low} mid {mid}->{mid + 1} high {high} [{string.Join(", ", a)}]");
mid++;
break;
default:
(a[mid], a[high]) = (a[high], a[mid]);
Console.WriteLine($"a[mid]=2 swap into the 2s low {low} mid {mid} high {high}->{high - 1} [{string.Join(", ", a)}]");
high--;
break;
}
}
Console.WriteLine($"\ndone: [{string.Join(", ", a)}]");Ele imprime:
start: [2, 0, 2, 1, 1, 0, 2, 1, 0]
a[mid]=2 swap into the 2s low 0 mid 0 high 8->7 [0, 0, 2, 1, 1, 0, 2, 1, 2]
a[mid]=0 swap into the 0s low 0->1 mid 0->1 high 7 [0, 0, 2, 1, 1, 0, 2, 1, 2]
a[mid]=0 swap into the 0s low 1->2 mid 1->2 high 7 [0, 0, 2, 1, 1, 0, 2, 1, 2]
a[mid]=2 swap into the 2s low 2 mid 2 high 7->6 [0, 0, 1, 1, 1, 0, 2, 2, 2]
a[mid]=1 already correct low 2 mid 2->3 high 6 [0, 0, 1, 1, 1, 0, 2, 2, 2]
a[mid]=1 already correct low 2 mid 3->4 high 6 [0, 0, 1, 1, 1, 0, 2, 2, 2]
a[mid]=1 already correct low 2 mid 4->5 high 6 [0, 0, 1, 1, 1, 0, 2, 2, 2]
a[mid]=0 swap into the 0s low 2->3 mid 5->6 high 6 [0, 0, 0, 1, 1, 1, 2, 2, 2]
a[mid]=2 swap into the 2s low 3 mid 6 high 6->5 [0, 0, 0, 1, 1, 1, 2, 2, 2]
done: [0, 0, 0, 1, 1, 1, 2, 2, 2]Nove valores, nove iterações, e ele nunca compara dois elementos do array entre si.
Custo: tempo O(n), espaço O(1), e é estável no sentido que importa aqui — uma passada, sem recursão.
Use quando você estiver particionando em três grupos por um teste barato em cada elemento. O enquadramento clássico são as cores da bandeira; o enquadramento útil é less than pivot, equal to pivot, greater than pivot.
O que lembrar
-
Pontas opostas exige monotonicidade, não só estar ordenado. Mover
lopara a direita tem que empurrar sua quantidade para um lado e moverhipara a esquerda tem que empurrar para o outro. Confira isso antes de confiar no descarte. -
Dois ponteiros no mesmo sentido é a edição in-place.
wvai atrás der, então nada é sobrescrito antes de ser lido, e a cauda velha depois dewé proposital. -
Uma âncora repetida e um ponteiro repetido são dois bugs de duplicata diferentes. Consertar um não conserta o outro, e só um deles aparece num caso de teste pequeno.
-
1..nno enunciado significa que o array pode ser a própria hash table dele. Espaço O(1) em vez de O(n), e o laço de trocas é linear porque toda troca resolve um valor para sempre. -
Depois de trocar com
high,midnão anda. O valor que você acabou de receber nunca foi examinado. É um caractere de diferença e é o bug mais comum do padrão inteiro.
A parte 2 pega a mesma ideia de dois índices e faz os dois ponteiros viajarem no mesmo sentido, onde a distância entre eles é a resposta: janelas deslizantes, e o truque do no-máximo-K que transforma “exatamente K” numa subtração.