Cuente ventanas que cumplen una regla
El truco de como máximo K menos como máximo (K-1)
Cuente ventanas que cumplen una regla es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Contar, no medir
A veces debe contar los subarreglos que cumplen una regla, no encontrar el más largo. Un pequeño truco convierte esto en un trabajo sencillo con ventanas deslizantes. 🔢
El desafío de exactamente K
Contar directamente los subarreglos que tienen exactamente K elementos de cierto tipo resulta incómodo. El límite cambia constantemente, lo que dificulta usar una sola ventana limpia.
La reformulación de como máximo
Contar los subarreglos con como máximo K es mucho más fácil con una sola ventana. Al expandirla hacia la derecha, cada posición left válida produce un subarreglo que se puede contar.
El truco de la resta
Exactamente K equivale a atMost(K) menos atMost(K - 1). Dos conteos sencillos se combinan para obtener el resultado más difícil que realmente necesita.
answer = at_most(k) - at_most(k - 1)Construya la función auxiliar
Escriba una función que cuente los subarreglos con como máximo k elementos. Desliza una ventana y la reduce cada vez que el conteo supera k.
def at_most(k):
left = 0
total = 0Reduzca cuando se incumpla la regla
Expanda right y actualice la ventana. Mientras contenga más de k elementos, avance left para devolverla al rango permitido.
while count > k:
# remove a[left]
left += 1Añada el conteo de la ventana
Después de corregir la ventana, todo subarreglo que termine en right y empiece desde left en adelante es válido. Añada right menos left más uno.
total += right - left + 1Por qué funciona ese conteo
Para un right fijo, los inicios válidos son left, left+1 y así sucesivamente hasta right. Eso equivale exactamente a right - left + 1 subarreglos, todos con como máximo k elementos.
Combine las dos llamadas
Ejecute la función auxiliar dos veces y reste los resultados. Cada llamada cuesta O(n), por lo que el conteo completo de exactamente K sigue siendo lineal.
return at_most(k) - at_most(k - 1)Controle el caso límite
Cuando k es cero, atMost(k - 1) usaría menos uno. Gestione ese caso para que la función auxiliar siga devolviendo un conteo válido de cero.
Dónde se aplica
La idea de como máximo menos como máximo sirve para contar subarreglos con exactamente K valores distintos, K números impares o cualquier propiedad monótona de cada ventana.
Comprobación rápida
Quiere contar los subarreglos que contienen exactamente K elementos distintos.
Resumen
Contar exactamente K consiste simplemente en calcular atMost(K) menos atMost(K - 1). Cada función auxiliar desliza una ventana en O(n), así que el conteo completo sigue siendo lineal. ✅
Preguntas frecuentes
¿La lección «Cuente ventanas que cumplen una regla» es gratis?
Sí — el texto completo de «Cuente ventanas que cumplen una regla» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Cuente ventanas que cumplen una regla»?
El truco de como máximo K menos como máximo (K-1) Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «Cuente ventanas que cumplen una regla»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Sumas de ventanas de tamaño fijo
- Ventana variable con dos punteros
- Subcadena más larga sin repeticiones
- Cuente ventanas que cumplen una regla