Dados N números inteiros, existem 2 números cuja soma é igual a um dado número S?

No último post, usei o seguinte problema como exemplo:

Dados N números inteiros, existem 2 números cuja soma é igual a um dado número S?

A solução mais óbvia é testar todos os pares de números e foi demonstrado que o seguinte algoritmo tinha um tempo de execução O(N²).

1 2 3 4 5 6 7

bool VerificaPares(int* valores, int N, int S) { for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) if (valores[i]+valores[j] == S) return true; return false; }

A notação Ó-grande significa que o tempo de execução do algoritmo é no máximo proporcional a N².
Agora o desafio é: como fazer melhor para podermos suportar mais de 10000 números?

Nós queremos encontrar 2 números A e B, tal que A + B = S.
Suponham que S = 12 e temos os números: 1, -3, 10, 6, 7, -2 e 5. A resposta é positiva visto que 5 + 7 = 12. A = 5 e B = 7, B = S - A e A = S - B.
No algoritmo dado acima, o ciclo i determina o número A e o ciclo j procura se existe um número B válido. Nós conseguiríamos melhorar a performance do algoritmo se a procura por B, isto é S - A, fosse mais eficiente.

Será que ordenar ajuda?
Se ordenarmos os números por ordem crescente, estes ficam pela ordem -3, -2, 1, 5, 6, 7, 10. Depois podemos utilizar o método da pesquisa binária para verificar se S-A existe no array de números.
No entanto, temos de ter cuidado com o caso A = B. Se A=6, pesquisa binária irá encontrar S-A = 6 no array. No entanto só existe um 6, por isso 6+6 não é uma solução válida.

Existem inúmeros algoritmos de ordenação. As linguagens de programação costumam fornecer na sua biblioteca standard uma implementação de um algoritmo de ordenação com tempo O(N log N) no pior caso (worst case) ou pelo menos em média (average case). Ver Best, worst and average case na Wikipedia.
A título de exemplo, a biblioteca de algoritmos da STL do C++ fornece a função sort() que é extremamente rápida, enquanto que o Java tem o Arrays.sort().

Para cada um dos N números do array, é feita uma pesquisa binária. A pesquisa binária tem um tempo de execução logaritmico O(log N). A pesquisa binária também está disponível nas bibliotecas de C++ e Java. No caso do C++, destaco as 3 pesquisas binárias diferentes: binary_search(), lower_bound() e upper_bound().

O tempo total de execução é O(N * log N + N * log N) = O(N log N). Exemplo de implementação em C++:

1 2 3 4 5 6 7 8 9 10 11

bool VerificaParesNlogN(int* v, int N, int S) { sort(v, v+N); for (int i = 0; i < N; i++) { if (v[i] == S - v[i]) { // A == B ? if (i+1 < N && v[i] == v[i+1]) return true; } else if (binary_search(v, v+N, S-v[i])) return true; } return false; }

Eliminar a pesquisa binária
Na verdade, a pesquisa binária não é necessária. Recordemos o array ordenado: -3, -2, 1, 5, 6, 7, 10.
Se somarmos o máximo e o mínimo, -3 + 10 = 7 que é menor do que S (12). Assim, sabemos que é impossível o -3 ser útil porque se a sua soma com o valor máximo é menor do que S, então a sua soma com qualquer outro número também o vai ser. De modo análogo, se esta soma fosse maior do que S, saberíamos que o 10 era inútil.

Deste modo, podemos usar dois apontadores: um começa no início e outro começa no fim do array. Se a soma dos valores dos apontadores for menor do que S, então precisamos de aumentar o mínimo (A), se for maior, então precisamos de diminuir o máximo (B).

1 2 3 4 5 6 7 8 9 10 11 12 13 14

bool VerificaParesNlogNv2(int* v, int N, int S) { sort(v, v+N); int a = 0, b = N-1; while (a < b) { int soma = v[a] + v[b]; if (soma == S) return true; else if (soma < S) a++; else b--; } return false; }

Em cada passo, encontramos a solução, incrementamos a ou decrementamos b. Assim, o ciclo while tem no máximo N-1 iterações. Logo, o tempo de execução desta parte do algoritmo é linear - O(N).

O tempo total de execução é O(N + N log N) = O(N log N), pois a ordenação N log N domina o factor N. Apesar de não ter diminuido a complexidade temporal total, esta técnica é bastante útil noutras situações.

Hashing: uma abordagem diferente e O(N)
Ordenar ajudou, mas será que conseguimos melhorar a solução para O(N)? Para isso, temos de conseguir procurar B em tempo constante denotado O(1).

Se soubermos que os números do array estão contidos num intervalo pequeno, por exemplo entre 0 e 999, isto é fácil. Basta usarmos um array com 1000 posições onde marcamos se existe um número com um determinado valor. Exemplo em C++:

1 2 3 4 5 6 7 8 9 10

bool VerificaParesHash(int* v, int N, int S) { char hash[1000] = {}; // inicializa a 0 for (int i = 0; i < N; i++) { int b = S - v[i]; if (b >= 0 && b <= 999 && hash[b]) // b já foi visto antes? return true; hash[v[i]] = 1; // v[i] passa a estar disponível para o futuro } return false; }

Felizmente, existe uma estrutura de dados chamada Hash Table que permite inserir e procurar dados em tempo O(1) para o caso mais genérico em que os números podem ter qualquer valor. Esta é uma estrutura de dados que as linguagens de programação costumam fornecer nas suas bibliotecas standard. O Java possui a classe HashSet, mas o C++ só na última versão do standard, C++11, é que passou a disponibilizar a classe unordered_set.

Para cada número do array, efectuamos uma pesquisa e uma inserção na hash table. Assim, o tempo de execução total é O(N * (1+1)) = O(N). Esta abordagem necessita de memória adicional O(N) para armazenar os números na hash table.

Nota: o facto da hash table disponibilizar procuras e inserções em tempo constante - O(1) - não significa que seja instantâneo ou desprezável. Apenas quer dizer que não depende do tamanho do input. De facto, há situações em que o factor constante pode tornar uma abordagem O(N) mais lenta do que outra abordagem O(N log N) com um factor constante muito pequeno. Se houver dúvidas quanto ao factor constante, é melhor efectuar testes práticos de desempenho.

Se esta pergunta fosse feita numa entrevista
Passamos da abordagem trivial O(N²) para O(N), conseguindo suportar milhões de números em vez de apenas 10000. Assim, se numa entrevista de emprego fizessem esta pergunta, o uso de hashing é a abordagem que devemos usar sempre? A resposta é não.

O uso da hash table é a melhor abordagem tipicamente, mas, dependendo do contexto em que estamos, podemos ter restrições adicionais.

1. Se a memória disponível for escassa e não for permitido usar O(N) de memória extra para guardar a hash table. Neste caso, temos de trabalhar com o array que temos obtendo O(N log N).
2. Para além da restrição anterior, há situações em que não podemos alterar o array que nos é dado, logo não podemos ordenar também. Logo, resta-nos a solução O(N²).

Complicando mais um pouco...
Como vêem, este problema parece trivial mas permite múltiplas abordagens :-)
E se fosse pedido o número de pares de números cuja soma é menor ou igual a S? Qual será a melhor abordagem?