Two-Sum e Suas Muitas Variantes
Resolva two-sum, three-sum, four-sum e two-sum com array ordenado usando mapas hash e dois ponteiros, comparando custos de tempo e espaço.
Two-Sum e Suas Muitas Variantes é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
Soma de dois: o problema clássico de entrevistas
LeetCode 1 'Soma de dois': dado um vetor não ordenado e um alvo, retorne os índices de dois elementos cuja soma seja igual ao alvo. A abordagem de força bruta O(n²) verifica todos os pares. A abordagem ideal O(n) usa um mapa hash: para cada elemento x, verifique se target - x já existe no mapa. Se existir, retorne o par de índices. Caso contrário, armazene x e seu índice no mapa.
Soma de dois costuma ser o primeiro problema de uma entrevista — dominar esse problema sinaliza que você está pronto para avançar para problemas mais difíceis.
def twoSum(nums, target):
seen = {} # val -> index
for i, x in enumerate(nums):
complement = target - x
if complement in seen:
return [seen[complement], i]
seen[x] = i
return []
print(twoSum([2, 7, 11, 15], 9)) # [0, 1]
print(twoSum([3, 2, 4], 6)) # [1, 2]
print(twoSum([3, 3], 6)) # [0, 1]Por que o mapa hash funciona para soma de dois
O mapa hash armazena cada elemento visto até o momento. Ao processar o elemento x, se target - x estiver no mapa, esses dois elementos formam um par válido. É crucial verificar o complemento antes de armazenar x, evitando o caso em que um único elemento seja associado a si mesmo (por exemplo, se x == alvo/2, a verificação do mapa ocorre antes de x ser armazenado, portanto não haverá correspondência a menos que existam duas cópias).
# Trace two-sum on [2, 7, 11, 15], target=9
nums, target = [2, 7, 11, 15], 9
seen = {}
for i, x in enumerate(nums):
complement = target - x
print(f'i={i} x={x} complement={complement} seen={seen}')
if complement in seen:
print(f' Found: indices [{seen[complement]}, {i}]')
break
seen[x] = iSoma de dois em um vetor ordenado (dois ponteiros)
Se o vetor já estiver ordenado e você precisar dos índices dos valores (não dos índices originais), use a técnica dos dois ponteiros: ponteiros esquerdo e direito iniciados em extremidades opostas. Se a soma for igual ao alvo, retorne. Se a soma for pequena demais, avance o ponteiro esquerdo para a direita. Se a soma for grande demais, mova o ponteiro direito para a esquerda. Isso leva tempo O(n) e usa espaço O(1) — é melhor que a abordagem do mapa hash quando o vetor está ordenado e a memória é limitada.
def twoSumSorted(numbers, target):
lo, hi = 0, len(numbers) - 1
while lo < hi:
s = numbers[lo] + numbers[hi]
if s == target:
return [lo + 1, hi + 1] # 1-indexed as per LeetCode 167
elif s < target:
lo += 1
else:
hi -= 1
return []
print(twoSumSorted([2, 7, 11, 15], 9)) # [1, 2]
print(twoSumSorted([2, 3, 4], 6)) # [1, 3]
print(twoSumSorted([-1, 0], -1)) # [1, 2]Soma de três (LeetCode 15)
LeetCode 15 'Soma de três': encontre todas as trincas distintas cuja soma seja zero. Ordene o vetor, fixe um elemento por vez e aplique a técnica dos dois ponteiros no subvetor ordenado restante. Ignore valores duplicados para evitar trincas duplicadas. Tempo: O(n²) — ideal para este problema, já que a própria saída pode conter O(n²) trincas.
def threeSum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: # skip duplicates
continue
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s == 0:
result.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < 0:
lo += 1
else:
hi -= 1
return result
print(threeSum([-1, 0, 1, 2, -1, -4])) # [[-1,-1,2],[-1,0,1]]
print(threeSum([0, 0, 0, 0])) # [[0,0,0]]Soma de quatro (LeetCode 18)
LeetCode 18 'Soma de quatro': encontre todas as quad completas distintas cuja soma seja igual ao alvo. Estenda soma de três: fixe dois elementos com dois laços aninhados (ignorando duplicatas) e, em seguida, aplique a técnica dos dois ponteiros no subvetor interno. Tempo: O(n³). Para a soma de k elementos em geral, faça a recursão k-2 vezes e depois aplique dois ponteiros, obtendo tempo O(n^(k-1)).
def fourSum(nums, target):
nums.sort()
n, result = len(nums), []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, n-2):
if j > i+1 and nums[j] == nums[j-1]:
continue
lo, hi = j+1, n-1
while lo < hi:
s = nums[i]+nums[j]+nums[lo]+nums[hi]
if s == target:
result.append([nums[i],nums[j],nums[lo],nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < target: lo += 1
else: hi -= 1
return result
print(fourSum([1,0,-1,0,-2,2], 0))
# [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]Soma de dois mais próxima do alvo
Uma variante comum: encontre o par cuja soma seja mais próxima do alvo (ela pode não ser exatamente igual ao alvo). Ordene o vetor e use dois ponteiros. Acompanhe a soma mais próxima encontrada até o momento e atualize-a sempre que encontrar um par com uma diferença absoluta menor em relação ao alvo. Essa abordagem O(n log n) é direta após a ordenação.
def twoSumClosest(nums, target):
nums.sort()
lo, hi = 0, len(nums) - 1
best = float('inf')
best_pair = None
while lo < hi:
s = nums[lo] + nums[hi]
if abs(s - target) < abs(best - target):
best = s
best_pair = (nums[lo], nums[hi])
if s < target:
lo += 1
elif s > target:
hi -= 1
else:
return best_pair # exact match
return best_pair
print(twoSumClosest([1, 3, 4, 7, 10], 15)) # (7, 10) => 17, closest to 15
print(twoSumClosest([2, 5, 8, 11], 10)) # (2, 8) => 10, exact!Soma de dois com vários pares (todos os pares)
Para encontrar todos os pares cuja soma seja igual ao alvo: ordene o vetor e use dois ponteiros, coletando todos os pares. Depois de encontrar um par válido, ignore duplicatas nas duas extremidades antes de continuar. Isso resulta em O(n log n) para a ordenação mais O(n) para a varredura — O(n log n) no total. Usar um mapa hash para coletar pares também é válido, mas exige cuidado com duplicatas.
def twoSumAllPairs(nums, target):
nums.sort()
lo, hi = 0, len(nums) - 1
pairs = []
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
pairs.append((nums[lo], nums[hi]))
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < target:
lo += 1
else:
hi -= 1
return pairs
print(twoSumAllPairs([1,1,2,3,4,4,5], 5)) # [(1,4),(1,4)-deduped,(2,3)]
# After duplicate-skipping: [(1,4),(2,3)]Contar pares com soma menor que K
Outra variante: conte quantos pares têm soma menor que k. Ordene o vetor e use dois ponteiros. Quando nums[lo] + nums[hi] < k, todos os pares (lo, lo+1), (lo, lo+2), ..., (lo, hi) são válidos — isso corresponde a hi - lo pares. Avance lo. Caso contrário, reduza hi. Tempo total: O(n log n) para a ordenação mais O(n) para a contagem.
def countPairsLessThan(nums, k):
nums.sort()
lo, hi = 0, len(nums) - 1
count = 0
while lo < hi:
if nums[lo] + nums[hi] < k:
count += hi - lo # all (lo, lo+1)...(lo, hi) are valid
lo += 1
else:
hi -= 1
return count
print(countPairsLessThan([1, 3, 7, 11, 12], 10)) # (1,3),(1,7),(3,7) => 3
print(countPairsLessThan([3, 5, 2, 3], 7)) # (2,3),(2,3) => 2... verifySoma de dois com mapa hash: lidando com duplicatas
Quando o mesmo valor pode aparecer várias vezes e você precisa da contagem de pares válidos (não apenas saber se existem), armazene contagens de frequência no mapa. Para pares cujos dois elementos são iguais, a quantidade de pares para uma frequência f é f*(f-1)//2. Para pares cujos dois elementos são diferentes, multiplique suas frequências. Isso permite contar todos os pares válidos em O(n).
from collections import Counter
def countTwoSumPairs(nums, target):
freq = Counter(nums)
count = 0
seen = set()
for x in freq:
y = target - x
if y in freq and (x, y) not in seen:
if x == y:
count += freq[x] * (freq[x] - 1) // 2
else:
count += freq[x] * freq[y]
seen.add((x, y))
seen.add((y, x))
return count
print(countTwoSumPairs([1,1,2,3,4,4,3], 4))
# Pairs summing to 4: (1,3)x2x2=4, (0+more)...Reconhecendo variações do padrão de soma de dois
O padrão de soma de dois aparece sob muitas formas. Reconheça-o quando um problema pedir para encontrar dois ou mais elementos que satisfaçam uma relação numérica (soma, produto, diferença). A estratégia central é sempre: fixe um elemento e, em seguida, encontre seu complemento em uma estrutura pré-computada (mapa hash ou vetor ordenado + ponteiro). Estenda para a soma de k elementos fixando k-2 elementos com laços aninhados e aplicando o caso-base.
# Summary of approaches by scenario
scenarios = [
('Unsorted array, any indices, one pair', 'hash map O(n) time O(n) space'),
('Sorted array, any indices, one pair', 'two pointers O(n) time O(1) space'),
('All unique pairs summing to target', 'sort + two pointers O(n log n)'),
('Three numbers summing to zero (3-sum)', 'sort + fix + two pointers O(n^2)'),
('k numbers summing to target (k-sum)', 'sort + k-2 loops + two pointers O(n^(k-1))')
]
for scenario, approach in scenarios:
print(f'{scenario}\n => {approach}\n')Comunicação em entrevistas para soma de dois
Quando soma de dois aparecer em uma entrevista, explique seu raciocínio em voz alta: "Preciso de dois números cuja soma seja igual ao alvo. Para cada número x, preciso verificar se alvo-x existe. Posso responder a isso em O(1) com um mapa hash, obtendo tempo total O(n) e espaço O(n). Como alternativa, se o vetor estivesse ordenado, eu poderia usar dois ponteiros com espaço O(1)." Apresente as duas abordagens e pergunte se há restrições de espaço antes de escolher.
Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação abordados nesta lição.
Recapitulação da lição
Nesta lição, você aprendeu: a soma de dois elementos usa um mapa hash para verificar a existência do complemento em O(1), resultando em O(n) no total, para vetores ordenados, dois ponteiros alcançam espaço O(1) e a soma de três e a soma de quatro elementos são reduzidas à soma de dois elementos por meio de ordenação e laços aninhados, executando em O(n²) e O(n³), respectivamente. Em seguida, exploraremos padrões de contagem de frequências e agrupamento com defaultdict e Counter.
Perguntas Frequentes
A aula “Two-Sum e Suas Muitas Variantes” é grátis?
Sim — o texto completo de “Two-Sum e Suas Muitas Variantes” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “Two-Sum e Suas Muitas Variantes”?
Resolva two-sum, three-sum, four-sum e two-sum com array ordenado usando mapas hash e dois ponteiros, comparando custos de tempo e espaço. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “Two-Sum e Suas Muitas Variantes”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de DSA Interview Prep?
Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Internals de Funções Hash e Tratamento de Colisões
- Two-Sum e Suas Muitas Variantes
- Contagem e Agrupamento por Frequência
- Maior Sequência Consecutiva e Cache LRU