Cuente subarrays con una suma objetivo
Combine sumas prefijas con un mapa hash
Cuente subarrays con una suma objetivo es una lección gratuita de Competitive Programming Academy en CoddyKit. Esta es la lección 3 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 Competitive Programming Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Competitive Programming Academy incluye 4 lecciones en total.
Una pregunta más difícil
Ahora viene el giro: cuente cuántos subarreglos suman un objetivo k. Comprobar cada par es lento, pero las sumas de prefijos junto con un mapa hash lo resuelven. 🎯
Replantee el problema con prefijos
La suma de un subarreglo equivale a prefix[r + 1] menos prefix[l]. Por lo tanto, una suma de k significa que dos valores de prefijo difieren exactamente en k.
La transformación clave
Si el prefijo actual es P, necesita un prefijo anterior igual a P menos k. Esa transformación es todo el truco.
need = current_prefix - kCuente, no busque
En lugar de retroceder cada vez para buscar, recuerde cuántas veces ha aparecido cada valor de prefijo. Un conteo acumulado responde en O(1).
Use un mapa de frecuencias
Un diccionario asigna a cada valor de prefijo la cantidad de veces que lo ha visto. Este mapa convierte la búsqueda en un conteo instantáneo.
from collections import defaultdict
seen = defaultdict(int)Inicialice el prefijo vacío
Antes del bucle, registre que el prefijo 0 ha aparecido una vez. Esta inicialización permite contar los subarreglos que comienzan en el índice 0.
seen[0] = 1El bucle de una pasada
Para cada elemento, actualice el prefijo acumulado, sume el conteo del valor necesario y después registre el prefijo actual. Una sola pasada se encarga de todo.
total += x
count += seen[total - k]
seen[total] += 1Por qué importa el orden
Debe sumar al resultado antes de registrar el prefijo actual. De lo contrario, se incluye por error un intervalo de longitud cero y el conteo falla.
La ventaja de velocidad
Cada elemento requiere un trabajo constante, por lo que el conteo completo se ejecuta en O(n). Esto supera a la fuerza bruta de O(n²) con entradas grandes.
Los negativos también funcionan
A diferencia de las ventanas deslizantes, este método funciona perfectamente con números negativos, porque las diferencias de prefijos siguen siendo válidas sin importar los signos.
Un caso de uso clásico
Este patrón resuelve el famoso problema de los subarreglos cuya suma es k y muchas variantes disfrazadas en los jueces de programación competitiva.
Comprobación rápida
Su prefijo acumulado es P y el objetivo es k.
Resumen
Puede contar subarreglos cuya suma sea el objetivo en O(n) usando sumas de prefijos y un mapa de frecuencias. Inicialice el prefijo 0 y cuente antes de registrar. ✅
Preguntas frecuentes
¿La lección «Cuente subarrays con una suma objetivo» es gratis?
Sí — el texto completo de «Cuente subarrays con una suma objetivo» 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 Competitive Programming Academy, actualiza a CoddyKit PRO. El curso de Competitive Programming Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Cuente subarrays con una suma objetivo»?
Combine sumas prefijas con un mapa hash Practicas Competitive Programming Academy 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 Competitive Programming Academy?
No se requiere experiencia previa. Competitive Programming Academy 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 3 de 4.
¿Cuánto tiempo toma la lección «Cuente subarrays con una suma objetivo»?
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 Competitive Programming Academy?
Sí. Cada lección de Competitive Programming Academy 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
- Construya un array de sumas prefijas
- Sume cualquier rango mediante resta
- Cuente subarrays con una suma objetivo
- Arrays de diferencias para actualizaciones de rangos