Encontre 2 inteiros em uma matriz que somam SUM

Uma pergunta comum da entrevista para alunos de graduação em busca de estágio é “Dado um array não classificado de inteiros positivos, encontre 2 números que somam SUM.”

Eu vejo muitas soluções onde quer que eu olhe na web. O mais simples e óbvio é O (n ^ 2). Alguns incluem classificação primeiro (que é O (nlogn) pelo menos). Outros produzem matrizes de contagem, matrizes de índice, etc.

De longe, o mais inteligente é usar uma tabela hash. Produzir uma tabela de hash perfeita custaria muito tempo, é pelo menos uma quantidade de tempo constante. Mas as tabelas de hash, em sua essência, são apenas matrizes. Em vez de usar uma estrutura de dados Hash Table embutida, você mesmo pode criar um array e verificar o array conforme o percorre.

Escrita de código rápido abaixo:

typedef int bool;
enum { false, true };

#define ARRAY_LENGTH 7
int array[ARRAY_LENGTH] = {5, 12, 18, 4, 3, 27, 2};

bool function(int SUM) {
    int index[SUM];
    for(int i = 0; i < ARRAY_LENGTH; i++) {
        if( array[i] < SUM ) {
            if( index[SUM-array[i]] == true ) {
                printf("%d and %d add up to %d",array[i], SUM-array[i], SUM);
                return true;
            }
            index[array[i]] = true;
        }
    }
    return false;
}

Esta não é apenas uma função O (n), mas para imediatamente ao encontrar o primeiro par de números, em vez de continuar por todo o array.