Conte Subarrays com uma Soma-Alvo

Agora vem a reviravolta: conte quantos subvetores somam um alvo k. Verificar todos os pares é lento, mas somas de prefixos com um mapa hash resolvem o problema. 🎯

A soma de um subvetor é igual a prefix[r + 1] menos prefix[l]. Portanto, uma soma igual a k significa que dois valores de prefixo diferem exatamente em k.

Se o prefixo atual é P, você precisa de um prefixo anterior igual a P menos k. Essa reorganização é todo o segredo.

Em vez de voltar e percorrer os valores a cada vez, registre quantas vezes cada valor de prefixo apareceu. Uma contagem acumulada responde em O(1).

Um dicionário associa cada valor de prefixo ao número de vezes que você o viu. Esse mapa transforma a busca em uma contagem instantânea.

Antes do laço, registre que o prefixo 0 apareceu uma vez. Esse valor inicial permite contar subvetores que começam no índice 0.

Para cada elemento, atualize o prefixo acumulado, adicione a contagem do valor necessário e depois registre o prefixo atual. Uma única passagem faz tudo.

Você deve adicionar à resposta antes de registrar o prefixo atual. Caso contrário, um intervalo de comprimento zero entra indevidamente e a contagem fica errada.

Cada elemento exige trabalho constante, então a contagem inteira é executada em O(n). Isso supera a força bruta O(n ao quadrado) para entradas grandes.

Ao contrário das janelas deslizantes, este método lida tranquilamente com números negativos, porque as diferenças de prefixos continuam válidas independentemente dos sinais.

Este padrão resolve o famoso problema de subvetores cuja soma é igual a k e muitas variações disfarçadas em avaliadores de competições.

Seu prefixo acumulado é P e o alvo é k.

Você pode contar subvetores com a soma desejada em O(n) usando somas de prefixos e um mapa de frequências. Inicialize o prefixo 0 e conte antes de registrar. ✅