Este problema pede para contar quantos subarrays conttínuos em um array dado somam um valor específico k.

Abordagem 1: Soma de Prefixos Bruta

Uma maneira direta é calcular a soma de prefixos de todo o aray. A soma de um subarray de índice i a j (inclusive) pode ser encontrada subtraindo a soma de prefixo até i-1 da soma de prefixo até j. Iteramos por todas as combinações possíveis de i e j e verificamos se a diferença das somas de prefixo é igual a k.

class SolucaoSomaPrefixoBruta {
public:
    int contarSubarraySoma(vector<int>& nums, int k) {
        int tamanho = nums.size();
        vector<int> prefixoSomas(tamanho + 1, 0);
        int contador = 0;

        // Calcula as somas de prefixo
        for (int i = 0; i < tamanho; ++i) {
            prefixoSomas[i + 1] = prefixoSomas[i] + nums[i];
        }

        // Verifica todos os subarrays possíveis
        for (int i = 0; i <= tamanho; ++i) {
            for (int j = i + 1; j <= tamanho; ++j) {
                if (prefixoSomas[j] - prefixoSomas[i] == k) {
                    contador++;
                }
            }
        }
        return contador;
    }
};

Abordagem 2: Soma de Prefixos com Mapa de Hash

A abordagem anterior tem uma complexidade de tempo de O(n²), o que pode ser muito lento para entradas grandes. Podemos otimizar isso usando um mapa de hash para armazenar as frequências das somas de prefixo encontradas até agora. A ideia é que, se a soma de prefixo até o índice atual for somaAtual, e quisermos que a soma de um subarray terminando neste índice seja k, então a soma de prefixo anterior necessária seria somaAtual - k. Podemos verificar no mapa de hash quantas vezes essa soma de prefixo anterior ocorreu. Se ocorreeu x vezes, isso significa que existem x subarrays terminando no índice atual que somam k.

Inicializamos o mapa de hash com {0, 1} para lidar com casos em que um subarray começando do início do array soma k.

#include <vector>
#include <unordered_map>

class SolucaoHashSomaPrefixo {
public:
    int contarSubarraySoma(vector<int>& nums, int k) {
        int tamanho = nums.size();
        unordered_map<int, int> frequenciaSomaPrefixo;
        int somaAtual = 0;
        int contador = 0;

        frequenciaSomaPrefixo[0] = 1; // Para casos onde o subarray começa do índice 0

        for (int i = 0; i < tamanho; ++i) {
            somaAtual += nums[i];
            int diferenca = somaAtual - k;

            // Se encontramos uma soma de prefixo anterior que, quando subtraída
            // da soma atual, resulta em k, adicionamos a contagem dessa soma
            // de prefixo anterior ao nosso resultado.
            if (frequenciaSomaPrefixo.count(diferenca)) {
                contador += frequenciaSomaPrefixo[diferenca];
            }

            // Incrementa a frequência da soma de prefixo atual no mapa
            frequenciaSomaPrefixo[somaAtual]++;
        }

        return contador;
    }
};

Considerações sobre Implementação

Na implementação original, a diferença entre as variáveis membro (res em uma versão) e as variáveis locais pode afetar o desempenho devido a otimizações do compilador. Variáveis locais geralmente podem ser alocadas em registradores, tornando o acesso mais rápido do que acessar variáveis membro que podem exigir desreferenciamento de ponteiro this. Para problemas com grandes restrições de tempo, a abordagem de mapa de hash O(n) é altamente recomendada em vez das abordagens O(n²) que podem levar a tempos limite (Time Limit Exceeded - TLE).