Conte Janelas que Satisfazem uma Regra
Use o truque de no máximo K menos no máximo (K-1).
Conte Janelas que Satisfazem uma Regra é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 4 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.
Contar, não medir
Às vezes é preciso contar subvetores que atendem a uma regra, e não encontrar o mais longo. Um pequeno truque transforma isso em um trabalho simples com janela deslizante. 🔢
O desafio de exatamente K
Contar diretamente subvetores com exatamente K ocorrências de algo é complicado. O limite fica mudando, o que dificulta criar uma única janela simples.
A reformulação como no máximo
Contar subvetores com no máximo K é muito mais fácil com uma única janela. À medida que você expande a direita, cada posição inicial válida fornece um subvetor contado.
O truque da subtração
Exatamente K é igual a atMost(K) menos atMost(K - 1). Duas contagens fáceis se combinam para produzir aquela que você realmente deseja.
answer = at_most(k) - at_most(k - 1)Crie a função auxiliar
Escreva uma função que conte subvetores com no máximo k elementos. Ela desliza uma janela e a reduz sempre que a contagem ultrapassa k.
def at_most(k):
left = 0
total = 0Reduza quando houver violação
Expanda a direita e atualize a janela. Enquanto ela contiver mais que k elementos, avance a esquerda para trazê-la de volta ao intervalo permitido.
while count > k:
# remove a[left]
left += 1Adicione a contagem da janela
Depois de corrigir a janela, todo subvetor que termina na direita e começa da esquerda em diante é válido. Adicione direita menos esquerda mais um.
total += right - left + 1Por que essa contagem funciona
Para uma direita fixa, os inícios válidos são esquerda, esquerda+1 e assim por diante até direita. Isso corresponde exatamente a right - left + 1 subvetores, todos satisfazendo a condição de no máximo k.
Combine as duas chamadas
Execute a função auxiliar duas vezes e subtraia os resultados. Cada chamada é O(n), portanto a contagem completa de exatamente K continua linear.
return at_most(k) - at_most(k - 1)Trate o caso extremo
Quando k é zero, atMost(k - 1) usaria menos um. Trate esse caso para que a função auxiliar ainda retorne uma contagem zero coerente.
Onde isso se aplica
A ideia de no máximo menos no máximo se aplica à contagem de subvetores com exatamente K valores distintos, K números ímpares ou qualquer propriedade monotônica por janela.
Verificação rápida
Você quer contar subvetores com exatamente K elementos distintos.
Recapitulação
Contar exatamente K é simplesmente atMost(K) menos atMost(K - 1). Cada função auxiliar desliza uma janela em O(n), portanto a contagem completa continua linear. ✅
Perguntas Frequentes
A aula “Conte Janelas que Satisfazem uma Regra” é grátis?
Sim — o texto completo de “Conte Janelas que Satisfazem uma Regra” é 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 “Conte Janelas que Satisfazem uma Regra”?
Use o truque de no máximo K menos no máximo (K-1). 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 4 de 4.
Quanto tempo leva a aula “Conte Janelas que Satisfazem uma Regra”?
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