Minimum Size Subarray Sum

Q: ¿Cuál es la complejidad temporal de la suma de subarreglo de tamaño mínimo?

La solución de ventana deslizante se ejecuta en tiempo O(n) y espacio O(1) . El bucle interno parece que podría hacer que la complejidad fuera cuadrática, pero left solo avanza, así que en toda la ejecución avanza como máximo n veces. La versión con suma de prefijos es O(n log n) , y comprobar cada inicio es O(n²) .

Q: ¿La submatriz tiene que sumar exactamente el objetivo?

No. Cualquier suma mayor o igual que target cuenta. Con target = 15 , la ventana 9, 3, 7 suma 19 y sigue teniendo una longitud de 3. Si necesitas una suma exacta, la ventana también funciona con valores positivos: reduce la ventana mientras la suma esté por encima del objetivo y registra una longitud solo cuando sea igual.

MedioVentana deslizante Suma de prefijos

+10

Recibes un entero positivo target y un arreglo nums de enteros positivos. Encuentra el subarreglo más corto (una secuencia de elementos contiguos) cuya suma sea al menos target y devuelve su longitud. Si ningún subarreglo alcanza target, devuelve 0.

Función

minSubArrayLen(target: integer, nums: integer-array) → integer

targetinteger: la suma que debe alcanzar o superar un subarreglo
numsinteger-array: el arreglo de enteros positivos
Devuelveinteger: la longitud del subarreglo más corto cuya suma sea al menos igual al objetivo, o 0 si no existe ninguno

Restricciones

1 ≤ target ≤ 10⁹
1 ≤ nums.length ≤ 2 × 10⁴
1 ≤ nums[i] ≤ 10⁴

Ejemplos

Entrada: target = 15nums = [4, 2, 9, 3, 7, 1, 5]
Salida: 3
Explicación: Ningún par de vecinos alcanza 15: el par más grande es 9 + 3 = 12. Tres sí lo alcanzan: 4 + 2 + 9 = 15 y 9 + 3 + 7 = 19, así que la respuesta es 3.

+16 pruebas ocultas al enviar

Para ir más allá

¿Cómo lo resolverías si nums también pudiera contener ceros y números negativos, y la ventana deslizante dejara de funcionar?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Todos los valores son positivos, así que ampliar un subarreglo siempre aumenta su suma y acortarlo siempre la reduce. Ese único hecho permite ambas soluciones rápidas. Las sumas de prefijos se convierten en una lista ordenada, así que una búsqueda binaria encuentra dónde una suma alcanza por primera vez target. Mejor aún, el mejor extremo nunca se mueve hacia la izquierda cuando el inicio se mueve hacia la derecha, así que una sola ventana que crece por la derecha y se reduce por la izquierda encuentra la respuesta en una pasada.

Extiende desde cada inicio

Correcto, pero no termina con las pruebas más grandes

Intuición

Fija un índice inicial y añade valores uno por uno hacia la derecha. La primera vez que la suma acumulada alcanza target, tienes el subarreglo más corto que empieza en ese índice: todos los más cortos se detuvieron antes y su suma seguía siendo demasiado pequeña. Así que registra su longitud, deja de extenderlo y pasa al siguiente índice inicial. La respuesta es la longitud más pequeña entre todos los índices iniciales.

Con target = 15 y [4, 2, 9, 3, 7, 1, 5], desde el índice 0 las sumas son 4, 6, 15 y se detiene en una longitud de 3. Desde el índice 1 las sumas son 2, 11, 14, 21 y se detiene en una longitud de 4. Desde el índice 2 las sumas son 9, 12, 19; longitud 3 otra vez. Ningún índice inicial obtiene un resultado mejor que 3.

El problema surge cuando es difícil alcanzar el objetivo. Si ningún subarreglo lo alcanza, cada índice inicial recorre todo el resto del arreglo: n(n+1)/2 sumas, que son 2 × 10^8 para n = 2 × 10^4. Además, cada índice inicial vuelve a calcular sumas que el índice anterior ya había calculado.

Algoritmo

Establece best en 0, lo que significa que todavía no se ha encontrado nada.
Para cada índice inicial, establece una suma acumulada en 0.
Mueve un índice final hacia la derecha desde el inicio, sumando nums[end] a la suma.
Cuando la suma alcance target, conserva end-start+1 si supera a best y deja de extender este inicio.
Devuelve best.

def minSubArrayLen(target, nums):
    n = len(nums)
    best = 0  # 0 means no subarray found yet
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            if total >= target:
                # The shortest subarray from this start ends here
                if best == 0 or end - start + 1 < best:
                    best = end - start + 1
                break
    return best

Suma de prefijos y búsqueda binaria

Intuición

Sea prefix[k] la suma de los primeros k valores, con prefix[0] = 0. La suma de nums[start..end-1] es entonces prefix[end] - prefix[start]. Para un inicio fijo, quieres el end más pequeño tal que prefix[end] ≥ prefix[start] + target.

Todos los valores son positivos, así que prefix es estrictamente creciente, y encontrar la primera posición en la que alcanza un valor requiere una búsqueda binaria. Para [4, 2, 9, 3, 7, 1, 5], prefix es [0, 4, 6, 15, 18, 25, 26, 31]. Desde el inicio 2 necesitas 6 + 15 = 21; el primer valor de prefix que es al menos 21 es 25 en el índice 5, así que la ventana es nums[2..4] = 9, 3, 7, de longitud 3.

Si incluso prefix[n] es menor que lo que necesita un inicio, ningún end sirve para ese inicio, y tampoco sirve ninguno para cualquier inicio posterior, ya que prefix[start] solo aumenta. Detente ahí. Son n búsquedas binarias, un tiempo de O(n log n), más O(n) para el arreglo de prefijos. El valor más grande que se compara es 2 × 10^8 + 10^9, que cabe en un entero de 32 bits.

Algoritmo

Construye prefix de longitud n+1, con prefix[k+1] = prefix[k] + nums[k].
Para cada inicio, calcula need = prefix[start] + target.
Si prefix[n] < need, detente: ningún inicio posterior puede dar resultado.
Busca mediante búsqueda binaria en las posiciones de start+1 a n el primer end para el que prefix[end] ≥ need, y conserva end-start si es el más corto hasta el momento.
Devuelve la longitud más corta, o 0 si ningún inicio dio resultado.

from bisect import bisect_left


def minSubArrayLen(target, nums):
    n = len(nums)
    # prefix[k] is the sum of the first k values; it only grows
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    best = 0
    for start in range(n):
        need = prefix[start] + target
        if prefix[n] < need:
            break  # no window from here on can reach target
        # The first end with prefix[end] >= need closes the shortest window
        end = bisect_left(prefix, need, start + 1)
        if best == 0 or end - start < best:
            best = end - start
    return best

Ventana deslizante

Intuición

Mantén una ventana nums[left..right] y su suma. Avanza right un paso a la vez y suma el nuevo valor. Mientras la suma sea al menos target, la ventana es una candidata: registra su longitud, luego elimina nums[left] y avanza left para ver si una ventana más corta sigue funcionando.

¿Por qué left puede salir definitivamente? Cuando la ventana nums[left..right] alcanza por primera vez target, la ventana más pequeña nums[left..right-1] no lo alcanzaba, porque el bucle la habría reducido en el paso anterior. Así que right es el extremo final más temprano para este inicio, y cualquier extremo final posterior solo da un subarreglo más largo. El inicio ya ha dado su mejor respuesta. Este argumento requiere valores positivos: con un número negativo, una ventana más larga podría tener después una suma mayor.

Con target = 15 y [4, 2, 9, 3, 7, 1, 5]: la suma sube a 4, 6, 15, así que se registra la longitud 3 y se elimina 4 (11). Al sumar 3 da 14; al sumar 7 da 21: registra la longitud 4, elimina 2 (19), registra la longitud 3 y elimina 9 (10). Al sumar 1 y 5 da 16: registra la longitud 4 y elimina 3 (13). La respuesta es 3.

El bucle while está dentro del bucle for, pero cada índice entra en la ventana una vez y sale una vez, así que el trabajo total es O(n). Solo se almacenan tres números, lo que ocupa O(1) espacio.

Algoritmo

Establece left = 0, total = 0 y best = 0.
Para cada right, suma nums[right] a total.
Mientras total ≥ target, conserva right-left+1 si supera a best, resta nums[left] y mueve left un paso hacia la derecha.
Devuelve best, que sigue siendo 0 si la suma nunca alcanzó target.

def minSubArrayLen(target, nums):
    best = 0  # 0 means no window found yet
    total = 0  # sum of nums[left .. right]
    left = 0
    for right in range(len(nums)):
        total += nums[right]
        # Shrink while the window still reaches target
        while total >= target:
            if best == 0 or right - left + 1 < best:
                best = right - left + 1
            total -= nums[left]
            left += 1
    return best

Errores comunes y casos límite

La mayoría de los errores están en el paso de reducción y en el valor que devuelves cuando nada alcanza target.

Reducir con if en vez de con while. Para target = 12 y [1, 1, 2, 3, 12], sumar 12 da como resultado 19. Un if registra la longitud 5, elimina un valor y continúa, por lo que nunca se mide la ventana [12] de longitud 1. Un bucle sigue eliminando valores mientras la suma siga siendo suficiente.
Registrar la longitud después de eliminar nums[left] en vez de hacerlo antes. La ventana que mides debe ser aquella cuya suma alcanzó target.
Comparar con > en vez de con ≥. Un subarreglo cuya suma es igual a target cuenta: [3, 3, 3] con target = 9 tiene como respuesta 3, no 0.
Devolver el valor centinela. Si inicializas best con n+1 o con infinito, conviértelo en 0 cuando nada haya alcanzado target.
Reutilizar la ventana en arreglos con ceros o números negativos. El método depende de que todos los valores sean positivos; este problema lo garantiza, pero las variantes no.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de la suma de subarreglo de tamaño mínimo?

La solución de ventana deslizante se ejecuta en tiempo O(n) y espacio O(1). El bucle interno parece que podría hacer que la complejidad fuera cuadrática, pero left solo avanza, así que en toda la ejecución avanza como máximo n veces. La versión con suma de prefijos es O(n log n), y comprobar cada inicio es O(n²).

¿Por qué la ventana deslizante necesita números positivos?

Reducir la ventana tiene que disminuir su suma y ampliarla tiene que aumentarla, o eliminar el elemento de la izquierda podría descartar el inicio de la respuesta. Con números negativos, ese orden se rompe. La solución habitual son las sumas de prefijos con una deque monótona de inicios candidatos, que sigue ejecutándose en O(n).

¿Por qué aprender la solución de suma de prefijos O(n log n) si existe una O(n)?

Los entrevistadores suelen preguntarlo después de la respuesta O(n). Muestra un segundo uso de los valores positivos: las sumas de prefijos están ordenadas, así que una búsqueda binaria encuentra dónde un total acumulado supera por primera vez un umbral. Esa herramienta vuelve a aparecer en otros problemas, como elegir un índice al azar en proporción a su peso.

¿La submatriz tiene que sumar exactamente el objetivo?

No. Cualquier suma mayor o igual que target cuenta. Con target = 15, la ventana 9, 3, 7 suma 19 y sigue teniendo una longitud de 3. Si necesitas una suma exacta, la ventana también funciona con valores positivos: reduce la ventana mientras la suma esté por encima del objetivo y registra una longitud solo cuando sea igual.

Python

def minSubArrayLen(target, nums):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

target = 15
nums = [4, 2, 9, 3, 7, 1, 5]

Esperado

Minimum Size Subarray Sum

Función

Restricciones

Ejemplos

Pistas

Solución

Extiende desde cada inicio

Suma de prefijos y búsqueda binaria

Ventana deslizante

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares