A maioria das perguntas de entrevista do tipo "faça em uma única passagem" tem a mesma resposta: lembre o que você já viu em um dicionário ou em um conjunto, usando como chave algo que possa ser consultado em um único passo.
- Conjunto de itens vistos: primeira repetição, duplicatas, "já vimos este id antes?".
- Busca do complemento: para dois valores que somam um alvo, guarde a posição de cada valor e, para cada novo valor, procure
target - value.
- Chave de agrupamento: coloque os itens que andam juntos sob a mesma chave, como anagramas sob suas letras ordenadas.
- Contagens: um
Counter responde "primeiro item que aparece uma vez" em duas passagens.
- Conjunto de todos os valores: deixa você iniciar uma sequência só no primeiro valor dela (
x - 1 fora do conjunto), de modo que a maior sequência de números consecutivos leva O(n).
A habilidade está em escolher a chave. Pergunte-se: o que preciso encontrar na hora quando o próximo item chegar?
Saída: (1, 3). Quando o 9 chega, seu par, o 7, já está no dicionário.