Reconhecendo problemas de array
O objetivo desta seção não é decorar a solução de 8 problemas — é você sair daqui resolvendo qualquer problema de array, inclusive os difíceis que nunca viu. Esta aula ensina o método; as próximas, os padrões.
Cada aula de padrão começa com um desafio 🎯 Tente primeiro: você tenta resolver antes de ver a teoria. Não pule — sentir a dificuldade é o que faz a ideia encaixar depois. (Se ainda não viu a seção Comece aqui, vale a pena começar por lá.)
Por que array é a primeira seção
Quase todo problema de LeetCode passa por um array em algum momento. Os cinco padrões que você vai aprender aqui — hash map, two pointers, sliding window, prefix e Kadane — reaparecem disfarçados em strings, matrizes, intervalos e até em árvores. Dominar esta seção é dominar o alicerce.
O método geral (serve para qualquer problema)
Diante de qualquer enunciado de array, siga estes 4 passos. Eles são o "algoritmo para escolher o algoritmo":
Passo 1 — Resolva no braço primeiro
Pegue o exemplo do enunciado e resolva na mão, sem código. Se você não consegue resolver com papel e caneta, nenhum padrão vai salvar. Esse passo também revela os casos especiais: array vazio? um elemento só? números negativos? duplicados?
Passo 2 — Escreva a força bruta (mentalmente)
Qual é a solução burra que testa tudo? Quase sempre é "para cada elemento, olhe todos os outros" — dois loops, O(n²). Ela é seu ponto de partida, não sua vergonha: numa entrevista, falar a força bruta primeiro mostra que você entendeu o problema.
Passo 3 — Ache o desperdício
Esta é a pergunta de ouro: que trabalho a força bruta repete sem necessidade? Cada padrão da seção elimina um tipo específico de desperdício:
| O desperdício da força bruta | O padrão que o elimina |
|---|---|
| "Procuro o mesmo valor várias vezes" | Hash map — lembre o que já viu |
| "Comparo pares que obviamente não podem ser a resposta" | Two pointers — descarte candidatos em bloco |
| "Recalculo a janela inteira que mal mudou" | Sliding window — atualize só a borda |
| "Resomo o mesmo intervalo várias vezes" | Prefix — pré-calcule acumulados |
| "Reavalio todos os começos de subarray" | Kadane — decida localmente: estender ou recomeçar |
Passo 4 — Confira contra os limites
O enunciado sempre diz o tamanho máximo da entrada — e isso dita a complexidade que você precisa (lembra da tabela de Big-O?):
| Limite de n | Complexidade necessária | Tradução |
|---|---|---|
| n ≤ ~500 | O(n²) ou até O(n³) passa | força bruta pode bastar |
| n ≤ ~100.000 | O(n log n) | provavelmente tem um sort no caminho |
| n ≤ ~1.000.000 | O(n) ou O(n log n) | precisa de um dos padrões |
Se sua solução é O(n²) e n vai a 10⁵, você já sabe o veredito antes de submeter: Time Limit Exceeded. Volte ao passo 3.
O método em ação (sem spoiler)
Pegue o problema clássico: "encontre dois números que somam um alvo" (Two Sum). Aplicando o método:
- No braço:
[2, 7, 11, 15], alvo 9 → 2 + 7 = 9. Fácil manualmente: você olha um número e procura o que falta. - Força bruta: para cada
nums[i], percorra o resto procurandoalvo - nums[i]. Dois loops, O(n²). - Desperdício: a cada volta eu procuro de novo, do zero, um valor no array — sendo que já passei por ele! Se eu lembrasse o que já vi, a busca seria instantânea.
- Limites: n até 10⁴ — O(n²) até passa raspando, mas o follow-up da entrevista é certo: "consegue fazer em uma passada?"
"Lembrar o que já vi com busca instantânea" tem nome: hash map — a próxima aula. Cada aula de padrão desta seção segue essa mesma trilha: primeiro o desperdício, depois a ideia que o elimina, depois os problemas onde ela brilha.
Os 8 problemas da seção
Estes são os problemas do Top 75 que vamos usar como exemplos dos padrões (o objetivo é o padrão, não o problema):
- Two Sum e Contains Duplicate → hash map
- Container With Most Water e 3Sum → two pointers
- Best Time to Buy and Sell Stock → sliding window / mínimo móvel
- Product of Array Except Self → prefix e suffix
- Maximum Subarray e Maximum Product Subarray → Kadane
E na prova final: três problemas inéditos para você aplicar tudo isso sem rede de proteção.
🧠 Quiz de fixação
0/31. Qual é a 'pergunta de ouro' do passo 3 do método, depois de pensar na força bruta?
2. O enunciado diz n ≤ 100.000 e sua solução é O(n²). O que você conclui ANTES de submeter?
3. Num problema, você percebe que a força bruta fica procurando, repetidamente, se um valor existe no array. Qual padrão ataca exatamente esse desperdício?
Resumo
- O método: resolver no braço → força bruta → achar o desperdício → conferir limites.
- Os limites do enunciado ditam a complexidade necessária.
- Os 5 padrões da seção são 5 respostas a 5 desperdícios diferentes.
Próxima aula: o padrão mais usado do LeetCode inteiro — hash map.