Quando me deparei com o “Two Sum” numa entrevista, a primeira coisa que me bateu na cabeça foi o velho duplo for. Dois loops aninhados, O(n²) puro, fazendo o processador gemer enquanto o array cresce. Mil elementos? Quase um milhão de comparações desperdiçadas, além de cache miss, branch misprediction e tudo mais. É o tipo de crime contra a performance que deixa qualquer dev de C a coçar a cabeça e a morder a língua.
A solução “na lata” seria percorrer tudo duas vezes, mas isso é um puxadinho que só funciona em provas de conceito. O que realmente salva o dia é trocar a busca cega por memória. Em vez de perguntar “qual será o outro número?”, pergunto “já vi algum número que, somado ao atual, dê o alvo?”. Cada iteração deixa um rastro, um registro de valor → índice. Quando o próximo elemento chega, basta olhar se o seu complemento já está nesse rastro. Se estiver, bingo! Temos os dois índices. É como um caixa‑eletrônico que guarda o histórico de notas já sacadas, antes de abrir o cofre ele verifica se já tem a combinação certa.
Em C não existe std::unordered_map pronto, então montei meu próprio “hash”* usando um vetor de structs. Cada entrada guarda o valor observado e o índice onde ele apareceu:
typedef struct {
int value; // número já visto
int index; // índice correspondente
} Entry;
A parte delicada é a gestão manual de memória. Aloco um vetor de Entry com tamanho igual ao do input (malloc(numsSize * sizeof(Entry))). Cada vez que encontro um novo número, insiro uma nova Entry no final do vetor (seenLen++). Quando o algoritmo termina, seja encontrando o par ou esgotando o array, libero essa memória (free(seen)) para não deixar sujeira na heap.
A assinatura da função LeetCode exige que eu devolva um ponteiro para um array de dois índices e preencha *returnSize. Isso implica outra alocação (malloc(2 * sizeof(int))) que o chamador deve liberar depois.
/*
* twoSum - devolve os índices de dois números que somam `target`.
*
* nums, numsSize, target, returnSize – parâmetros de entrada/saída.
* Retorna ponteiro para vetor de 2 ints; o chamador libera com `free()`.
*/
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
Entry *seen = (Entry*)malloc(numsSize * sizeof(Entry));
int seenLen = 0;
*returnSize = 2;
int *result = (int*)malloc(2 * sizeof(int));
for (int i = 0; i < numsSize; i++) {
int complement = target - nums[i];
for (int j = 0; j < seenLen; j++) {
if (seen[j].value == complement) {
result[0] = seen[j].index;
result[1] = i;
free(seen);
return result;
}
}
seen[seenLen].value = nums[i];
seen[seenLen].index = i;
seenLen++;
}
free(seen);
return result;
}
Matematicamente, a busca interna ainda é linear, logo no pior caso o algoritmo permanece O(n²). Na prática, porém, a constante é drasticamente menor que a do duplo for, a maioria dos complementos é encontrada cedo, e o vetor seen nunca cresce tanto quanto o número total de iterações quadráticas. Se substituirmos o laço interno por uma tabela hash real, cadeia ou sondagem, a complexidade cairia para O(n) puro, com acesso médio O(1).
Espacialmente gastamos O(n) bytes para guardar até n entradas. É o preço que pagamos por velocidade, mais memória, menos tempo de CPU. Em C isso significa vigiar os malloc/free. Qualquer caminho que retorne antes de liberar seen precisa garantir a limpeza, caso contrário, um pequeno leak pode virar um pesadelo de memory bloat em programas de longa execução.
No fim das contas, memória em C não é só espaço, é informação. Mantendo um histórico dos valores já vistos transformamos a procura em consulta. Essa troca, gastar alguns kilobytes para ganhar tempo de CPU.. é o pulo do gato que faz toda a diferença. Se ainda estiveres a usar o duplo for, sente a dor do cache thrashing e lembra, cada detalhe de alocação bem tratado salva horas de depuração.
Espero que esse raciocínio te poupe alguns ciclos de CPU e muita dor de cabeça. No fim, programar em C é isso.. domar o caos da memória com um pouco de estratégia.
Bons estudos e que o seu
heapesteja sempre limpo!