Introdução
Bem-vindos ao 11º artigo da nossa estimada “Série Preparação para Entrevistas“. Hoje, discutiremos o problema do “Two Sum”.
Este problema, com o qual já me deparei em entrevistas técnicas, será o foco deste artigo, onde demonstrarei como resolvê-lo de forma eficiente e eficaz. Exploraremos três estratégias distintas, cada uma acompanhada de uma análise detalhada de sua eficiência e complexidade. Com o objetivo de tornar este guia extremamente prático e aplicável, forneceremos soluções codificadas não só apenas Java mas também em Python, que é uma linguagem que estou estudando.
Vamos lá!
Explicação do Problema
O objetivo deste problema é simples, mas sua solução pode variar em complexidade. Dado um array de números inteiros e um valor alvo, nossa tarefa é encontrar dois números dentro do array cuja soma seja igual ao valor alvo.
Por exemplo, considere o array [13, 4, 7, 6, 18] e o valor alvo 19. Neste caso, os números 6 e 13 somam 19, que é o nosso valor alvo.
Implementação com Loops Aninhados
Nossa primeira solução para o desafio “Two Sum” utiliza uma abordagem direta e simples. Ela consiste em percorrer o array com dois loops aninhados, verificando se algum par de números soma exatamente o valor alvo.
Implementação em Java
import java.util.Arrays;
public class SomaDoisNumeros {
public static int[] encontraSoma(int[] array, int somaAlvo) {
for (int i = 0; i < array.length; i++) {
for (int j = i + 1; j < array.length; j++) {
int somaAtual = array[i] + array[j];
if (somaAtual == somaAlvo) {
return new int[]{array[i], array[j]};
}
}
}
return new int[]{};
}
public static void main(String[] args) {
int[] numeros = {13, 6, 7, 18, 4};
int somaAlvo = 19;
System.out.println(Arrays.toString(encontraSoma(numeros, somaAlvo)));
}
}
Implementação em Python
def encontra_soma(array, soma_alvo):
for i in range(len(array)):
for j in range(i + 1, len(array)):
soma_atual = array[i] + array[j]
if soma_atual == soma_alvo:
return [array[i], array[j]]
return []
# Exemplo de uso
numeros = [13, 6, 7, 18, 4]
soma_alvo = 19
print(encontra_soma(numeros, soma_alvo))Análise da Complexidade
Esta solução tem uma complexidade de tempo O(n²), onde n é o número de elementos no array. A complexidade surge do fato de que para cada elemento do array, precisamos verificar sua soma com cada um dos outros elementos. Apesar de ser fácil de implementar, essa abordagem se torna menos eficiente à medida que o tamanho do array aumenta.
A complexidade de espaço é O(1), já que não utilizamos estruturas de dados adicionais além do array de entrada.
Solução Utilizando Ponteiros
Uma maneira mais eficiente de resolver o problema “Two Sum” é utilizando uma combinação de ordenação do array e o uso de dois ponteiros. Esta abordagem reduz significativamente a complexidade de tempo em comparação com a solução anterior de dois loops aninhados.
Ordenar o Array: Primeiramente, ordenamos o array.
Usar Dois Ponteiros: Inicializamos dois ponteiros – um no início do array e outro no final. Movemos esses ponteiros de acordo com a soma dos valores que eles apontam em relação ao valor alvo:
- Se a soma for menor que o valor alvo, incrementamos o ponteiro esquerda (para aumentar a soma).
- Se a soma for maior, movemos o ponteiro, decrementamos o ponteiro da direita(para diminuir a soma).
- Se a soma for igual ao valor alvo, encontramos a solução.
Implementação em Java
import java.util.Arrays;
public class SomaDoisNumeros {
public static int[] encontraSoma(int[] array, int somaAlvo) {
Arrays.sort(array);
int esquerda = 0;
int direita = array.length - 1;
while (esquerda < direita) {
int somaAtual = array[esquerda] + array[direita];
if (somaAtual == somaAlvo) {
return new int[] {array[esquerda], array[direita]};
} else if (somaAtual < somaAlvo) {
esquerda++;
} else {
direita--;
}
}
return new int[]{};
}
public static void main(String[] args) {
int[] numeros = {13, 6, 7, 18, 4};
int somaAlvo = 19;
System.out.println(Arrays.toString(encontraSoma(numeros, somaAlvo)));
}
}
Implementação em Python
def encontra_soma(array, soma_alvo):
array.sort()
esquerda, direita = 0, len(array) - 1
while esquerda < direita:
soma_atual = array[esquerda] + array[direita]
if soma_atual == soma_alvo:
return [array[esquerda], array[direita]]
elif soma_atual < soma_alvo:
esquerda += 1
else:
direita -= 1
return []
# Exemplo de uso
numeros = [13, 6, 7, 18, 4]
soma_alvo = 19
print(encontra_soma(numeros, soma_alvo))
Análise da Complexidade
Complexidade de Tempo
A complexidade de tempo é O(n log n) devido à necessidade de ordenar o array. A busca utilizando dois ponteiros é O(n), mas a ordenação é o passo que domina a complexidade de tempo.
Complexidade de Espaço
É O(1) se a ordenação for realizada in-place, ou seja, sem utilizar estruturas adicionais significativas.
Implementação Utilizando Um HashSet
A terceira abordagem para resolver o problema “Two Sum” envolve o uso de um HashSet, que permite verificar de forma eficiente se um certo complemento(diferença) do valor alvo já foi visto no array. Esta é uma abordagem mais eficiente em termos de tempo de execução, mas precisamos utilizar uma estrutura de dados adicional.
Implementação em Java
import java.util.HashSet;
import java.util.Set;
public class SomaDoisNumeros {
public static int[] encontraSoma(int[] array, int somaAlvo) {
Set<Integer> numerosVisitados = new HashSet<>();
for (int num : array) {
int diferenca = somaAlvo - num;
if (numerosVisitados.contains(diferenca)) {
return new int[] {diferenca, num};
}
numerosVisitados.add(num);
}
return new int[]{};
}
}
Implementação em Python
def encontra_soma(array, soma_alvo):
numeros_visitados = set()
for num in array:
diferenca = soma_alvo - num
if diferenca in numeros_visitados:
return [diferenca, num]
numeros_visitados.add(num)
return []
# Exemplo de uso
numeros = [13, 6, 7, 18, 4]
soma_alvo = 21
print(encontra_soma(numeros, soma_alvo))
Análise de Complexidade
Complexidade de Tempo
O(n), onde n é o número de elementos no array. Cada elemento é processado uma única vez.
Complexidade de Espaço
O(n), devido ao armazenamento de elementos no HashSet.
Conclusão
Ao longo deste artigo, exploramos três abordagens distintas para resolver o clássico problema “Two Sum” em entrevistas técnicas. Cada solução ofereceu um equilíbrio único entre complexidade de implementação e eficiência de execução, destacando a importância de entender diferentes estratégias.
- Solução com Dois Loops Aninhados: Simples de entender e implementar, mas com uma complexidade de tempo O(n²), tornando-a menos ideal para arrays grandes.
- Solução com Dois Ponteiros: Uma melhoria significativa em termos de eficiência, reduzindo a complexidade de tempo para O(n log n). Esta abordagem é mais adequada para situações onde a ordenação do array não é uma limitação.
- Uso de HashSet: Oferece a melhor eficiência em termos de tempo de execução com uma complexidade de O(n). É a solução ideal quando a eficiência de tempo é a principal preocupação e podemos tolerar um aumento na complexidade de espaço.
A escolha da abordagem correta depende do contexto específico do problema e das restrições de desempenho. Em entrevistas técnicas, demonstrar a capacidade de escolher e implementar a estratégia mais adequada pode ser tão importante quanto a própria solução.
Encorajo você a experimentar estas soluções por conta própria. Se você tiver dúvidas, sugestões ou experiências para compartilhar, deixe um comentário abaixo. Sua participação é uma parte valiosa deste aprendizado coletivo.
Esperamos que este artigo tenha enriquecido seu conhecimento e preparo para suas próximas entrevistas técnicas. Fique atento para mais artigos desta série, onde continuaremos a desvendar outros desafios comuns de programação.
Quer praticar esse tipo de problema do jeito que cai em entrevistas?
Estou construindo o DevPrep, uma plataforma em português focada em raciocínio e padrões de algoritmos.
👉 Acesso por beta fechado: https://devprep.dev/
Referências
Cracking the Coding Interview’ é um best-seller renomado e um favorito pessoal – um livro indispensável na preparação para entrevistas técnicas!
Designing Data-Intensive Applications: é uma referência para criar aplicações escaláveis, robustas e de alto desempenho!