Minimum Size Subarray Sum

Q: Qual é a complexidade de tempo de Subarray Sum de Tamanho Mínimo?

A solução de janela deslizante é executada em tempo O(n) e usa espaço O(1) . O loop interno parece que poderia torná-la quadrática, mas left só avança, então, ao longo de toda a execução, ele avança no máximo n vezes. A versão com soma de prefixos é O(n log n) , e verificar cada posição inicial é O(n²) .

Q: Por que aprender a solução de soma de prefixos O(n log n) se existe uma O(n)?

Entrevistadores costumam pedir isso depois da resposta O(n) . Isso mostra um segundo uso de valores positivos: as somas prefixadas ficam ordenadas, então uma busca binária encontra onde um total acumulado ultrapassa um limite pela primeira vez. Essa ferramenta volta a aparecer em outros problemas, como escolher um índice aleatoriamente em proporção ao seu peso.

Q: A subarray precisa somar exatamente o valor-alvo?

Não. Qualquer soma maior ou igual a target conta. Com target = 15 , a janela 9, 3, 7 soma 19 e ainda tem comprimento 3. Se você precisar de uma soma exata, a janela ainda funciona para valores positivos: diminua a janela enquanto a soma estiver acima do alvo e registre um comprimento somente quando ela for igual.

MédioJanela deslizante Soma de prefixos

+10

Você recebe um inteiro positivo target e um array nums de inteiros positivos. Encontre o subarray mais curto (uma sequência de elementos vizinhos) cuja soma seja pelo menos target e retorne seu comprimento. Se nenhum subarray atingir target, retorne 0.

Função

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

targetinteger: a soma que um subarray deve alcançar ou ultrapassar
numsinteger-array: o array de números inteiros positivos
Retornainteger: o comprimento da menor submatriz cuja soma seja pelo menos igual a target, ou 0 se nenhuma existir

Restrições

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

Exemplos

Entrada: target = 15nums = [4, 2, 9, 3, 7, 1, 5]
Saída: 3
Explicação: Nenhum par de vizinhos chega a 15: o maior par é 9 + 3 = 12. Três chegam: 4 + 2 + 9 = 15 e 9 + 3 + 7 = 19, então a resposta é 3.

+16 testes ocultos ao enviar

Para ir além

Como você resolveria isso se nums também pudesse conter zeros e números negativos, situação em que a janela deslizante deixa de funcionar?

Dicas

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

0 de 3 abertas

Solução

Todos os valores são positivos, então estender um subarray sempre aumenta sua soma, e cortá-lo sempre a diminui. Esse único fato é a base das duas soluções rápidas. As somas de prefixo se tornam uma lista ordenada, então uma busca binária encontra onde uma soma atinge target pela primeira vez. Melhor ainda, o melhor fim nunca se move para a esquerda quando o início se move para a direita, então uma única janela que cresce à direita e encolhe à esquerda encontra a resposta em uma única passagem.

Expanda a partir de cada início

Correta, mas não termina nos maiores testes

Intuição

Fixe um índice inicial e adicione os valores um a um, avançando para a direita. Na primeira vez que a soma acumulada alcançar target, você terá o subarray mais curto que começa nesse índice: todos os mais curtos terminaram antes, e suas somas ainda eram pequenas demais. Então, registre seu comprimento, pare de estender e passe para o próximo índice inicial. A resposta é o menor comprimento entre todos os índices iniciais.

Com target = 15 e [4, 2, 9, 3, 7, 1, 5], o índice inicial 0 produz as somas 4, 6, 15 e para no comprimento 3. O índice inicial 1 produz as somas 2, 11, 14, 21 e para no comprimento 4. O índice inicial 2 produz as somas 9, 12, 19, novamente com comprimento 3. Nenhum índice inicial consegue um resultado melhor que 3.

O problema surge quando é difícil alcançar o alvo. Se nenhum subarray o alcançar, cada índice inicial percorre todo o restante do array: n(n+1)/2 adições, o que dá 2 × 10^8 para n = 2 × 10^4. Cada índice inicial também recalcula somas que o índice anterior já havia calculado.

Algoritmo

Defina best como 0, significando que nada foi encontrado ainda.
Para cada índice inicial, defina uma soma acumulada como 0.
Mova um índice final para a direita a partir do início, adicionando nums[end] à soma.
Quando a soma atingir target, mantenha end-start+1 se superar best e pare de estender esse início.
Retorne 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

Somas prefixadas e busca binária

Intuição

Seja prefix[k] a soma dos primeiros k valores, com prefix[0] = 0. A soma de nums[start..end-1] é, então, prefix[end] - prefix[start]. Para um start fixo, você quer o menor end tal que prefix[end] ≥ prefix[start] + target.

Todos os valores são positivos, então prefix é estritamente crescente, e encontrar a primeira posição em que ele atinge um valor é uma busca binária. Para [4, 2, 9, 3, 7, 1, 5], prefix é [0, 4, 6, 15, 18, 25, 26, 31]. A partir de start 2, você precisa de 6 + 15 = 21; o primeiro prefixo maior ou igual a 21 é 25 no índice 5, então a janela é nums[2..4] = 9, 3, 7, com comprimento 3.

Se até mesmo prefix[n] for menor que o valor necessário para um start, nenhum end funciona para ele, e nenhum funciona para qualquer start posterior, pois prefix[start] só aumenta. Pare nesse ponto. Isso significa n buscas binárias, tempo O(n log n), mais O(n) para o array de prefixos. O maior valor comparado é 2 × 10^8 + 10^9, que cabe em um inteiro de 32 bits.

Algoritmo

Crie prefix com comprimento n+1, com prefix[k+1] = prefix[k] + nums[k].
Para cada início, calcule need = prefix[start] + target.
Se prefix[n] < need, pare: nenhum início posterior poderá dar certo.
Faça uma busca binária nas posições de start+1 a n para encontrar o primeiro end com prefix[end] ≥ need e mantenha end-start se for o menor até então.
Retorne o menor comprimento ou 0 se nenhum início tiver dado certo.

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

Janela deslizante

Intuição

Mantenha uma janela nums[left..right] e sua soma. Avance right uma posição por vez e some o novo valor. Enquanto a soma for pelo menos target, a janela é uma candidata: registre seu comprimento, depois remova nums[left] e avance left para ver se uma janela menor ainda funciona.

Por que left pode sair de vez? Quando a janela nums[left..right] atinge target pela primeira vez, a janela menor nums[left..right-1] não atingiu, pois o loop a teria reduzido na etapa anterior. Portanto, right é o fim mais cedo para esse início, e qualquer fim posterior só produz um subarray mais longo. Esse início já forneceu sua melhor resposta. Esse argumento exige valores positivos: com um número negativo, uma janela mais longa poderia ter uma soma maior posteriormente.

Para target = 15 e [4, 2, 9, 3, 7, 1, 5]: a soma aumenta para 4, 6, 15, então o comprimento 3 é registrado e 4 sai (11). Adicionar 3 resulta em 14; adicionar 7 resulta em 21: registre o comprimento 4, remova 2 (19), registre o comprimento 3, remova 9 (10). Adicionar 1 e 5 resulta em 16: registre o comprimento 4, remova 3 (13). A resposta é 3.

O loop while fica dentro do loop for, mas cada índice entra na janela uma vez e sai dela uma vez, então o trabalho total é O(n). Apenas três números são armazenados, o que ocupa espaço O(1).

Algoritmo

Defina left = 0, total = 0 e best = 0.
Para cada right, adicione nums[right] a total.
Enquanto total ≥ target, mantenha right-left+1 se for maior que best, subtraia nums[left] e mova left um passo para a direita.
Retorne best, que ainda será 0 se a soma nunca atingir 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

Armadilhas e casos extremos

A maioria dos bugs está na etapa de encolhimento e no valor retornado quando nada atinge target.

Encolher usando if em vez de while. Para target = 12 e [1, 1, 2, 3, 12], adicionar 12 faz a soma chegar a 19. Um if registra o comprimento 5, remove um valor e segue em frente, então a janela [12], de comprimento 1, nunca é medida. Um loop continua removendo enquanto a soma ainda for suficiente.
Registrar o comprimento depois de remover nums[left] em vez de antes. A janela medida deve ser aquela cuja soma atingiu target.
Comparar com > em vez de ≥. Um subarray cuja soma é igual a target conta: [3, 3, 3] com target = 9 tem resposta 3, não 0.
Retornar o sentinela. Se você inicializar best com n+1 ou infinito, converta-o para 0 quando nada tiver atingido target.
Reutilizar a janela em arrays com zeros ou números negativos. Ela depende de todos os valores serem positivos; este problema garante isso, mas outras variantes não.

Perguntas frequentes4

Qual é a complexidade de tempo de Subarray Sum de Tamanho Mínimo?

A solução de janela deslizante é executada em tempo O(n) e usa espaço O(1). O loop interno parece que poderia torná-la quadrática, mas left só avança, então, ao longo de toda a execução, ele avança no máximo n vezes. A versão com soma de prefixos é O(n log n), e verificar cada posição inicial é O(n²).

Por que a janela deslizante precisa de números positivos?

Diminuir a janela precisa reduzir sua soma, e aumentá-la precisa elevá-la; caso contrário, descartar o elemento da esquerda poderia eliminar o início da resposta. Com números negativos, essa ordem deixa de funcionar. A solução usual é usar somas prefixadas com uma deque monotônica de inícios candidatos, o que ainda funciona em O(n).

Por que aprender a solução de soma de prefixos O(n log n) se existe uma O(n)?

Entrevistadores costumam pedir isso depois da resposta O(n). Isso mostra um segundo uso de valores positivos: as somas prefixadas ficam ordenadas, então uma busca binária encontra onde um total acumulado ultrapassa um limite pela primeira vez. Essa ferramenta volta a aparecer em outros problemas, como escolher um índice aleatoriamente em proporção ao seu peso.

A subarray precisa somar exatamente o valor-alvo?

Não. Qualquer soma maior ou igual a target conta. Com target = 15, a janela 9, 3, 7 soma 19 e ainda tem comprimento 3. Se você precisar de uma soma exata, a janela ainda funciona para valores positivos: diminua a janela enquanto a soma estiver acima do alvo e registre um comprimento somente quando ela for igual.

Python

def minSubArrayLen(target, nums):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

Minimum Size Subarray Sum

Função

Restrições

Exemplos

Dicas

Solução

Expanda a partir de cada início

Somas prefixadas e busca binária

Janela deslizante

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos