Síntese: qual padrão usar?
Você conhece os 5 padrões. Falta a habilidade que vale a entrevista: bater o olho num enunciado novo e saber qual usar — com justificativa.
A árvore de decisão da seção
Diante de um problema de array, percorra estas perguntas em ordem:
1. A pergunta é sobre um TRECHO CONTÍGUO (subarray)?
├── Sim, e os valores são todos positivos (ou janela de tamanho fixo)
│ → SLIDING WINDOW (estado entra/sai pelas bordas)
├── Sim, mas há NEGATIVOS
│ ├── "maior soma/produto" → KADANE (estender ou recomeçar)
│ └── "quantos somam k" /
│ perguntas de intervalo → PREFIX (+ hash map para contar)
└── Não, continue ↓
2. Procuro PARES/TRIOS de elementos?
├── Preciso de valores EXATOS (complemento) e/ou dos índices originais
│ → HASH MAP (pergunte ao passado, registre para o futuro)
└── Array ordenado (ou posso ordenar) / condição de DESIGUALDADE
→ TWO POINTERS (descarte provado em bloco)
3. Pergunto repetidamente "já vi? quantas vezes? existe?"
→ HASH MAP
4. "Para cada posição, algo sobre TODO o resto" (esquerda × direita)
→ PREFIX + SUFFIX (duas passadas)
E o teste de sanidade final, sempre: os limites. n até 10⁵-10⁶ pede O(n) ou O(n log n) — se o seu plano é O(n²), volte à árvore.
O mapa completo da seção
| Padrão | Desperdício que elimina | Pergunta-chave | Tempo | Espaço |
|---|---|---|---|---|
| Hash map | busca repetida | "já vi o que procuro?" | O(n) | O(n) |
| Two pointers | pares sem chance | "qual lado abandono — e por quê?" | O(n)* | O(1) |
| Sliding window | recálculo de janelas | "o que entra, o que sai?" | O(n) | O(1)** |
| Prefix/Suffix | resoma de trechos | "posso pré-acumular?" | O(n) | O(1)-O(n) |
| Kadane | reavaliar todo começo | "estendo ou recomeço?" | O(n) | O(1) |
* + O(n log n) se precisar ordenar antes. ** depende do estado da janela (um escalar = O(1); um mapa de contagens = O(k)).
Repare no que todos têm em comum: uma passada (ou duas) com trabalho O(1) por elemento, cada um com seu truque para nunca revisitar trabalho feito. Esse é o espírito de tudo que derrota O(n²).
Quiz da seção
O teste de verdade: enunciados que você não viu nas aulas. Para cada um, identifique o padrão — e, mais importante, saiba dizer o porquê. 7+ acertos: você está pronto para a prova final.
🧠 Quiz da seção: Array
0/101. 'Dado um array e k, retorne a MAIOR MÉDIA entre todos os subarrays de exatamente k elementos.' Qual padrão?
2. 'Num array ORDENADO, encontre dois números cuja soma é mais PRÓXIMA de zero.' Qual padrão e por quê?
3. 'Conte quantos subarrays contíguos têm soma exatamente k. O array tem números NEGATIVOS.' Qual padrão?
4. 'Encontre o subarray contíguo de maior soma' (com negativos). Qual padrão?
5. 'Para cada posição i, retorne a SOMA de todos os elementos exceto nums[i].' Qual abordagem O(n)?
6. 'Verifique se alguma dupla de elementos IGUAIS está a no máximo k posições de distância.' Qual padrão?
7. Sua solução é O(n²) e o enunciado diz n ≤ 10⁶. O que a árvore de decisão manda fazer?
8. 'Retorne os ÍNDICES de dois números (array NÃO ordenado) que somam o alvo.' Por que two pointers NÃO é a melhor escolha?
9. 'Maior PRODUTO de subarray contíguo' (com negativos). Qual o cuidado extra sobre o Kadane básico?
10. Qual é a ideia-mãe que TODOS os padrões da seção compartilham?
Pronto para a prova?
A prova final tem três problemas inéditos — um fácil, um médio e um difícil — com casos de teste ocultos, como no LeetCode real. Tudo que você precisa está nas 7 aulas desta seção (e uma dica honesta: a árvore de decisão lá de cima resolve a escolha do padrão dos três).
Boa prova! Volte para a página da seção e clique em "Prova final".