Encontre um Par com uma Soma Determinada
Supere a força bruta O(n^2).
Encontre um Par com uma Soma Determinada é uma aula grátis de Competitive Programming Academy 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 Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
O Problema da Soma de um Par
Dado um vetor e um alvo, encontre dois valores cuja soma seja igual a ele. Essa é uma das tarefas introdutórias mais comuns em competições. 🔍
A Abordagem por Força Bruta
A solução óbvia tenta cada par usando dois laços aninhados. Ela funciona, mas verificar todos os pares custa O(n^2) e pode ser lento demais.
for i in range(n):
for j in range(i + 1, n):
if a[i] + a[j] == target:
return (i, j)Onde a Força Bruta Falha
Com n próximo de 100000, O(n^2) representa dez bilhões de verificações, e você atingirá um TLE. As restrições estão indicando que você deve encontrar algo mais rápido.
Ordene e Depois Percorra
Se você sort o vetor primeiro, dois ponteiros nas duas extremidades resolvem o problema em uma única passagem. Ordenar custa O(n log n), e depois a varredura custa O(n).
a.sort()
left, right = 0, len(a) - 1Compare com o Alvo
A cada etapa, leia a[left] + a[right]. Esse único número determina seu próximo movimento, sem qualquer tentativa às cegas.
total = a[left] + a[right]Correspondência Exata: Concluído
Se a soma for igual ao alvo, você encontrou o par. Retorne-o imediatamente, pois você precisa apenas de uma resposta válida.
if total == target:
return (left, right)Caso Contrário, Ajuste
Se a soma for pequena demais, mova left para a direita; se for grande demais, mova right para a esquerda. A ordem crescente garante que cada movimento ajuda.
elif total < target:
left += 1
else:
right -= 1Não Existe Nenhum Par
Se os ponteiros se cruzarem sem encontrar uma correspondência, não existe nenhum par válido. O fim do laço já é, por si só, uma resposta completa.
A Alternativa do Conjunto de Dispersão
Se você precisar manter os índices originais, um conjunto de dispersão é mais simples: para cada valor, verifique se o alvo menos esse valor já foi visto.
seen = set()
for x in a:
if target - x in seen:
# found
pass
seen.add(x)Escolher o Método
Use dois ponteiros quando o vetor estiver ordenado ou puder ser ordenado; use o conjunto de dispersão quando precisar de O(n) verdadeiro sem ordenar ou tiver de manter os índices.
Fique Atento às Duplicatas
Se um valor puder formar um par com ele mesmo, certifique-se de que seus dois índices sejam diferentes. Uma verificação rápida com left != right ou i != j evita esse problema.
Verificação Rápida
Você quer superar a força bruta O(n^2) para encontrar um par cuja soma seja igual a um alvo.
Recapitulação
Ordene e percorra o vetor com dois ponteiros para encontrar um par correspondente ao alvo em O(n log n), ou use um conjunto de dispersão para obter O(n) quando os índices forem importantes. Escolha de acordo com as restrições. ✅
Perguntas Frequentes
A aula “Encontre um Par com uma Soma Determinada” é grátis?
Sim — o texto completo de “Encontre um Par com uma Soma Determinada” é 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 Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Encontre um Par com uma Soma Determinada”?
Supere a força bruta O(n^2). Você pratica Competitive Programming Academy 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 Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy 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 “Encontre um Par com uma Soma Determinada”?
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 Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy 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
- Dois Ponteiros em um Array Ordenado
- Encontre um Par com uma Soma Determinada
- Remova Duplicatas no Próprio Array
- Mescle Duas Sequências Ordenadas