Longest Subarray with Sum K

+10

Dado el arreglo de enteros nums y un objetivo k, devuelve la longitud del subarreglo más largo cuyos elementos suman exactamente k. Un subarreglo es un tramo de elementos consecutivos de al menos un elemento. Algunos valores pueden ser cero o menores que cero. Si ningún subarreglo suma k, devuelve 0.

Función

longestSubarrayWithSumK(nums: integer-array, k: integer) → integer

numsinteger-array: los números enteros que se van a buscar, incluidos los negativos y el cero
kinteger: la suma exacta que debe tener el subarreglo
Devuelveinteger: la longitud del subarreglo más largo cuya suma es k, o 0 si no existe ninguno

Restricciones

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
-10⁹ ≤ k ≤ 10⁹
Cada suma de prefijos se mantiene entre -2 × 10⁸ y 2 × 10⁸, así que los enteros de 32 bits son suficientes.
Devuelve 0 cuando ningún subarreglo sume k.

Ejemplos

Entrada: nums = [2, -1, 3, 1, -4, 2, 3]k = 5
Salida: 5
Explicación: Tres secuencias suman 5: [2, 3] al final, [2, -1, 3, 1] al principio y [3, 1, -4, 2, 3] en los índices del 2 al 6. La última es la más larga, con 5 elementos.

Entrada: nums = [4, 1, 1, 2, -1, 1]k = 3
Salida: 4
Explicación: [1, 1, 2, -1] en los índices del 1 al 4 y [1, 2, -1, 1] en los índices del 2 al 5 suman 3 con 4 elementos. Devuelves una longitud, así que el empate no importa.

Para ir más allá

¿Cómo encontrarías el subarreglo más largo cuya suma sea como máximo k, permitiendo que todavía haya valores negativos?

Pistas

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

0 de 3 abiertas

Solución

Los totales acumulados convierten la suma de cualquier subarreglo en una sola resta: los elementos después del índice s hasta el índice i suman prefix[i] - prefix[s]. Recuerda el primer índice donde aparece cada total, y una sola pasada encuentra la coincidencia más larga que termina en cada posición.

Extiende cada subarreglo desde cada punto de inicio

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

Intuición

Desde cada inicio, extiéndete hacia la derecha y suma cada elemento a un total acumulado. Cada vez que el total sea igual a k, registra la longitud. Cada subarreglo corresponde a un par de inicio y fin, así que no se omite ninguno. Sigue extendiéndote después de que el total supere k: desde el índice 2 del primer ejemplo, los totales son 3, 4, 0, 2, 5, y el -4 es la razón por la que el último llega a 5.

Hay alrededor de n²/2 pares: 2 × 10^8 sumas para n = 2 × 10^4.

Algoritmo

Establece best en 0.
Para cada start, establece total en 0.
Mueve end desde start hasta el último índice y suma nums[end] a total.
Cuando total sea igual a k, establece best en el mayor valor entre best y end - start + 1.
Devuelve best.

def longestSubarrayWithSumK(nums, k):
    n = len(nums)
    best = 0
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            # A match may come after the total has passed k, so never stop early
            if total == k and end - start + 1 > best:
                best = end - start + 1
    return best

Sumas prefijas con el primer índice de cada suma

Intuición

Un tramo que termina en el índice i suma k exactamente cuando algún total anterior es igual a prefix - k. Si varios totales anteriores cumplen esa condición, el primero inicia el tramo más largo, así que el mapa almacena cada total solo la primera vez que aparece. Una copia posterior solo podría iniciar un tramo más corto. Inicializa el mapa con el total 0 en el índice -1, para que una coincidencia que empieza en el índice 0 tenga longitud i + 1.

En el primer ejemplo, los totales son 2, 1, 4, 5, 1, 3, 6. En el índice 6, 6 - 5 = 1 apareció por primera vez en el índice 1, lo que da una longitud de 5. El total 1 vuelve a aparecer en el índice 4, y conservar el índice 1 es lo que permite encontrar ese tramo.

Una búsqueda por elemento da un tiempo O(n), y el mapa contiene como máximo n + 1 totales.

Algoritmo

Crea un mapa first que contenga el total 0 en el índice -1, y establece prefix y best en 0.
Para cada índice i, suma nums[i] a prefix.
Si prefix - k está en el mapa en el índice start, establece best en el mayor de best y i - start.
Si prefix aún no está en el mapa, guárdalo con el índice i.
Devuelve best.

def longestSubarrayWithSumK(nums, k):
    # first[p] is the index where the prefix sum p first appears; the empty prefix sits at -1
    first = {0: -1}
    prefix = 0
    best = 0
    for i, num in enumerate(nums):
        prefix += num
        # The earliest prefix equal to prefix - k starts the longest match that ends at i
        start = first.get(prefix - k)
        if start is not None and i - start > best:
            best = i - start
        # Keep the first index only: a later one could only start a shorter subarray
        if prefix not in first:
            first[prefix] = i
    return best

Errores comunes y casos límite

Sobrescribir el índice almacenado cada vez que se repite un total conserva el inicio más reciente y encuentra una coincidencia más corta. El primer ejemplo devuelve 4 en lugar de 5, porque el total 1 pasa del índice 1 al índice 4.
Una ventana que se reduce mientras su suma es mayor que k también devuelve 4 en el primer ejemplo. Termina con [-1, 3, 1, -4, 2, 3] y una suma de 4, y nunca elimina el -1.
Omitir el total 0 en el índice -1 hace que no se encuentre ninguna coincidencia que empiece en el índice 0: [5, 0, 0, 0] con k = 5 devuelve 0 en lugar de 4.
El índice almacenado es la posición anterior al subarreglo, así que la longitud es i - start. Sumar 1 cuenta un elemento de más.

Preguntas frecuentes3

¿Cuál es la complejidad temporal del subarreglo más largo con suma K?

Tiempo O(n) y espacio adicional O(n) con totales acumulados y un mapa de los primeros índices: una búsqueda y como máximo una inserción por elemento. Ampliar cada subarreglo desde cada posición inicial cuesta tiempo O(n²) y espacio O(1).

¿Por qué falla una ventana deslizante cuando el arreglo tiene números negativos?

Una ventana deslizante supone que agregar un elemento aumenta la suma y quitar uno la reduce. Con valores negativos, una ventana cuya suma es demasiado grande aún puede llegar a k cuando aparece un elemento negativo, y una cuya suma es demasiado pequeña quizá necesite quitar un elemento negativo de su izquierda. La ventana no puede determinar qué movimiento es el correcto.

¿Se puede resolver el problema de la subarray más larga con suma K usando O(1) de espacio adicional?

Solo cuando ningún valor es negativo. Entonces la suma nunca disminuye a medida que crece la ventana, y dos punteros encuentran la ventana más larga cuya suma es k en tiempo O(n) y espacio O(1). Con valores negativos necesitas el mapa de totales o el recorrido O(n²).

def longestSubarrayWithSumK(nums, k):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

nums = [2, -1, 3, 1, -4, 2, 3]
k = 5

Salida Esperada