24 de Março
Contém duplicata
Como sair do O(n²) e perceber que o problema só quer saber se você já viu esse valor.
Arrays e Conjunto Iniciante 10 min TypeScript
Dado um array de inteiros nums, retorne true se algum valor aparecer pelo menos duas vezes e false se todos os valores forem distintos.
Exemplo:
Input: nums = [1, 2, 3, 1]
Output: true
O que perceber antes de codar
- O problema pede uma resposta de sim ou não. Você não precisa contar tudo.
- Assim que encontrar uma repetição, pode parar.
- A pergunta central e: eu já vi este valor antes?
Erros comuns
- continuar percorrendo mesmo depois de achar uma duplicata
- ordenar o array cedo demais sem justificar por que mudou a abordagem
Passo 1 — Ler o que realmente esta sendo pedido
Não e um problema de contagem completa.
Não e um problema de achar todas as duplicatas.
O enunciado só quer saber se existe pelo menos uma repetição.
Isso importa porque muda o jeito de pensar:
- assim que você encontrar uma duplicata, já acabou
- você não precisa continuar processando o resto
Passo 2 — Escrever a versão mais simples
A primeira solução correta compara cada número com os seguintes:
export function containsDuplicate(nums: number[]): boolean {
for (let i = 0; i < nums.length; i += 1) {
for (let j = i + 1; j < nums.length; j += 1) {
if (nums[i] === nums[j]) {
return true
}
}
}
return false
}
Funciona. Mas você repete comparações demais.
Passo 3 — Reformular a pergunta
Em vez de perguntar "com quem este número combina?", aqui a pergunta e mais simples:
o número atual já apareceu antes?
Se você conseguisse responder isso na hora, não precisaria do segundo loop.
Passo 4 — Guardar o que já apareceu
Um conjunto hash resolve exatamente essa parte.
Enquanto percorre o array:
- se o valor já estiver no conjunto, existe duplicata
- se não estiver, adicione e continue
O problema inteiro vira uma passada com memória.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function containsDuplicate(nums: number[]): boolean {
// sua solução aqui
return false
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(n)
Espaço: O(n)
Solução 1 — Força bruta O(n²)
Dois loops aninhados. Para cada número, compare com todos os seguintes.
export function containsDuplicate(nums: number[]): boolean {
for (let i = 0; i < nums.length; i += 1) {
for (let j = i + 1; j < nums.length; j += 1) {
if (nums[i] === nums[j]) {
return true
}
}
}
return false
}Funciona. Mas cresce rápido demais porque o array e percorrido várias vezes.
Solução 2 — Conjunto hash em O(n)
Agora a pergunta fica mais alinhada com o problema real:
Eu já vi este valor antes?
Se a resposta puder sair em tempo constante, uma passada basta.
export function containsDuplicate(nums: number[]): boolean {
const seen = new Set<number>()
for (const value of nums) {
if (seen.has(value)) {
return true
}
seen.add(value)
}
return false
}O conjunto hash guarda os valores já vistos. Quando um valor reaparece, você descobre na hora.
O que dizer na entrevista
Uma explicação curta e boa seria:
A versão inicial compara cada número com todos os outros e custa
O(n²). Como eu só preciso saber se o valor atual já apareceu, uso umconjunto hashpara busca media emO(1)e resolvo em uma passada.
Isso mostra que você:
- entendeu a versão simples
- soube explicar por que ela desperdica trabalho
- escolheu a estrutura de dados certa para a pergunta real
Quando esse padrão aparece de novo
Esse raciocínio volta quando o problema pede:
- detectar repetição
- saber se algo já apareceu
- validar unicidade
- interromper cedo assim que a condição acontecer
O ponto não e decorar
conjunto hash.
O ponto e perceber quando o problema só precisa de memória do que já passou.