Longest Subarray with Sum K

+10

Dado o array de inteiros nums e um alvo k, retorne o comprimento do maior subarray cujos elementos somam exatamente k. Um subarray é uma sequência de elementos consecutivos, com pelo menos um elemento. Alguns valores podem ser zero ou negativos. Se nenhum subarray somar k, retorne 0.

Função

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

numsinteger-array: os números inteiros a serem pesquisados, incluindo negativos e zeros
kinteger: a soma exata que o subarray deve ter
Retornainteger: o comprimento do maior subarray cuja soma é k, ou 0 se nenhum tiver essa soma

Restrições

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
-10⁹ ≤ k ≤ 10⁹
Cada soma de prefixo permanece entre -2 × 10⁸ e 2 × 10⁸, então inteiros de 32 bits são suficientes.
Retorne 0 quando nenhum subarray somar k.

Exemplos

Entrada: nums = [2, -1, 3, 1, -4, 2, 3]k = 5
Saída: 5
Explicação: Três sequências somam 5: [2, 3] no final, [2, -1, 3, 1] no início e [3, 1, -4, 2, 3] nos índices de 2 a 6. A última é a mais longa, com 5 elementos.

Entrada: nums = [4, 1, 1, 2, -1, 1]k = 3
Saída: 4
Explicação: [1, 1, 2, -1] nos índices de 1 a 4 e [1, 2, -1, 1] nos índices de 2 a 5 somam 3 com 4 elementos. Você retorna um comprimento, então o empate não importa.

Para ir além

Como você encontraria o subarray mais longo cuja soma seja no máximo k, permitindo ainda valores negativos?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

As somas acumuladas transformam a soma de qualquer subarray em uma subtração: os elementos após o índice s até o índice i somam prefix[i] - prefix[s]. Lembre-se do primeiro índice em que cada total aparece, e uma única passagem encontra a correspondência mais longa que termina em cada posição.

Cresça cada subarray a partir de cada início

Correta, mas não termina nos maiores testes

Intuição

A partir de cada início, avance para a direita e adicione cada elemento a um total acumulado. Sempre que o total for igual a k, registre o comprimento. Cada subarray corresponde a um par de início e fim, então nenhum é ignorado. Continue avançando mesmo depois que o total ultrapassar k: a partir do índice 2 no primeiro exemplo, os totais são 3, 4, 0, 2, 5, e o -4 é o motivo pelo qual o último chega a 5.

Há cerca de n²/2 pares: 2 × 10^8 adições para n = 2 × 10^4.

Algoritmo

Defina best como 0.
Para cada start, defina total como 0.
Mova end de start até o último índice e some nums[end] a total.
Quando total for igual a k, defina best como o maior entre best e end - start + 1.
Retorne 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

Somas prefixadas com o primeiro índice de cada soma

Intuição

Um trecho que termina no índice i soma k exatamente quando algum total anterior é igual a prefix - k. Se vários totais anteriores forem válidos, o primeiro deles inicia o trecho mais longo, então o mapa armazena cada total apenas na primeira vez que aparece. Uma ocorrência posterior só poderia iniciar um trecho mais curto. Inicialize o mapa com o total 0 no índice -1, para que uma correspondência que começa no índice 0 tenha comprimento i + 1.

No primeiro exemplo, os totais são 2, 1, 4, 5, 1, 3, 6. No índice 6, 6 - 5 = 1 apareceu pela primeira vez no índice 1, o que resulta em comprimento 5. O total 1 reaparece no índice 4, e manter o índice 1 é o que permite encontrar esse trecho.

Uma consulta por elemento resulta em tempo O(n), e o mapa contém no máximo n + 1 totais.

Algoritmo

Crie um mapa first contendo o total 0 no índice -1 e defina prefix e best como 0.
Para cada índice i, adicione nums[i] a prefix.
Se prefix - k estiver no mapa no índice start, defina best como o maior entre best e i - start.
Se prefix ainda não estiver no mapa, armazene-o com o índice i.
Retorne 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

Armadilhas e casos extremos

Sobrescrever o índice armazenado cada vez que um total se repete mantém o início mais recente e encontra uma correspondência mais curta. O primeiro exemplo retorna 4 em vez de 5, porque o total 1 passa do índice 1 para o índice 4.
Uma janela que diminui enquanto sua soma está acima de k também retorna 4 no primeiro exemplo. Ela termina contendo [-1, 3, 1, -4, 2, 3] com soma 4 e nunca descarta o -1.
Deixar de fora o total 0 no índice -1 faz com que todas as correspondências que começam no índice 0 não sejam encontradas: [5, 0, 0, 0] com k = 5 retorna 0 em vez de 4.
O índice armazenado é a posição anterior ao subarray, então o comprimento é i - start. Somar 1 conta um elemento a mais.

Perguntas frequentes3

Qual é a complexidade de tempo do subarray mais longo com soma K?

Tempo O(n) e espaço extra O(n) com totais acumulados e um mapa dos primeiros índices: uma consulta e, no máximo, uma inserção por elemento. Expandir cada subarray a partir de cada início custa tempo O(n²) e espaço O(1).

Por que uma janela deslizante falha quando o array contém números negativos?

Uma janela deslizante pressupõe que adicionar um elemento aumenta a soma e remover um elemento a diminui. Com valores negativos, uma janela cuja soma é muito grande ainda pode chegar a k quando um elemento negativo chega, e uma janela cuja soma é muito pequena talvez precise remover um elemento negativo à esquerda. A janela não consegue determinar qual movimento é o correto.

É possível resolver o problema do subarray mais longo com soma K usando espaço extra O(1)?

Somente quando nenhum valor é negativo. Então, a soma nunca diminui à medida que a janela cresce, e dois ponteiros encontram a janela mais longa com soma k em O(n) de tempo e O(1) de espaço. Com valores negativos, você precisa do mapa de totais ou da varredura O(n²).

def longestSubarrayWithSumK(nums, k):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

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

Saída Esperada