Janela Variável com Dois Ponteiros
Aumente e diminua até satisfazer uma condição.
Janela Variável com Dois Ponteiros é 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.
Quando a janela respira
Alguns problemas não fixam o comprimento da janela. Em vez disso, a janela cresce e diminui para manter uma condição verdadeira, como uma soma que permanece abaixo de um limite.
Dois ponteiros, uma janela
Mantenha dois índices, esquerda e direita, marcando as bordas da janela. O ponteiro da direita expande a janela enquanto o da esquerda fica atrás para reduzi-la quando necessário.
left = 0
window = 0Expanda para a direita
Percorra todos os elementos para a direita e inclua cada um na janela. Atualize seu estado acumulado, como ao adicionar o novo valor a uma soma.
for right in range(n):
window += a[right]Reduza quando necessário
Enquanto a janela violar a regra, mova o ponteiro da esquerda para a direita e remova esse elemento. Isso restaura a condição sem precisar voltar.
while window > limit:
window -= a[left]
left += 1Leia a janela válida
Quando o laço interno termina, a janela da esquerda até a direita é válida. Seu comprimento é right menos left mais um, pronto para ser usado.
length = right - left + 1Registre o melhor resultado
Atualize sua resposta com essa janela válida, geralmente a mais longa encontrada. Faça isso a cada iteração para não deixar nada passar.
best = max(best, right - left + 1)Por que é linear
Cada ponteiro só se move para a frente, nunca para trás. Esquerda e direita avançam juntas no máximo n posições, portanto a varredura completa é O(n).
O requisito de monotonicidade
Isso funciona quando estender a janela apenas torna a condição mais difícil de satisfazer. É esse comportamento monotônico que permite que a esquerda nunca retroceda.
Mais longa versus mais curta
Para obter a janela válida mais curta, reduza-a enquanto a regra continuar valendo e registre o resultado antes de interromper. A mecânica dos ponteiros permanece a mesma.
while window >= target:
best = min(best, right - left + 1)
window -= a[left]
left += 1Cuidado com janelas vazias
Se a redução puder esvaziar a janela, proteja-se contra a esquerda ultrapassar a direita. Confirme também que uma resposta foi realmente encontrada antes de retorná-la.
Identifique o padrão
Recorra a uma janela variável quando o problema pedir o trecho contíguo mais longo ou mais curto que satisfaça uma condição sobre seus elementos.
Verificação rápida
Você executa uma janela variável com dois ponteiros sobre um vetor de tamanho n.
Recapitulação
Expanda a direita para incluir elementos, reduza a esquerda enquanto a regra for violada e registre cada janela válida. Ponteiros que só avançam mantêm a complexidade em O(n). ✅
Perguntas Frequentes
A aula “Janela Variável com Dois Ponteiros” é grátis?
Sim — o texto completo de “Janela Variável com Dois Ponteiros” é 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 “Janela Variável com Dois Ponteiros”?
Aumente e diminua até satisfazer uma condição. 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 “Janela Variável com Dois Ponteiros”?
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
- Somas em Janelas de Tamanho Fixo
- Janela Variável com Dois Ponteiros
- Maior Substring sem Repetições
- Conte Janelas que Satisfazem uma Regra