Numărul secvențelor cu suma k, în C++

În 1 -1 1, există trei secvențe cu suma 1: primul element, ultimul element și întregul vector. Numărăm intervale consecutive de poziții, nu selecții arbitrare. Valorile negative fac nepotrivită o regulă simplă de tip „suma a crescut prea mult, deci eliminăm din stânga”.

Diferența dintre două prefixe

Suma prefixului p[j] este suma primelor j elemente. Convenția p[0]=0 reprezintă prefixul gol. Suma intervalului care începe după prefixul i și se termină la prefixul j este p[j]-p[i]. Pentru a obține k, avem nevoie de p[i]=p[j]-k, cu i<j.

Citim 0≤n≤1000, k între -10^9 și 10^9, apoi n valori din același interval. Afișăm numărul secvențelor nevide cu suma k. Sumele prefix pot depăși tipul int, deci folosim long long. Tabloul clasic rezervă 1000 de celule, indicii utili fiind 0..n-1.

Păstrăm frecvențele prefixelor anterioare

Un map este aici un dicționar care asociază fiecărei sume numărul aparițiilor ei. Înaintea prelucrării avem o apariție a sumei zero, prefixul gol. Pentru fiecare sumă nouă căutăm câte prefixe anterioare au valoarea prefix-k și adăugăm acel număr la răspuns.

Abia după numărare introducem prefixul curent în dicționar. Dacă l-am introduce înainte, pentru k=0 am număra și intervalul gol dintre prefixul curent și el însuși.

Pentru 1,-1,1, prefixele sunt 0,1,0,1. Perechile de prefixe (0,1), (0,3), (2,3) au diferența 1.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
#include <map>
using namespace std;
int main() {
    int n; long long k; cin >> n >> k;
    long long a[1000];
    for(int i=0;i<n;++i) cin >> a[i];
    map<long long,long long> frecventa;
    frecventa[0]=1;
    long long prefix=0,raspuns=0;
    for(int i=0;i<n;++i) {
        prefix+=a[i];
        auto it=frecventa.find(prefix-k);
        if(it!=frecventa.end()) raspuns+=it->second;
        ++frecventa[prefix];
    }
    cout << raspuns << '\n';
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
#include <map>
using namespace std;
int main() {
    int n; long long k; cin >> n >> k;
    vector<long long> a(n);
    for(int i=0;i<n;++i) cin >> a[i];
    map<long long,long long> frecventa;
    frecventa[0]=1;
    long long prefix=0,raspuns=0;
    for(int i=0;i<n;++i) {
        prefix+=a[i];
        auto it=frecventa.find(prefix-k);
        if(it!=frecventa.end()) raspuns+=it->second;
        ++frecventa[prefix];
    }
    cout << raspuns << '\n';
}

De ce contează frecvența, nu simpla prezență

Pentru 0 0, sumele prefix sunt 0,0,0. La primul element găsim un prefix anterior cu suma zero, iar la al doilea găsim două. Răspunsul este 1+2=3. Un dicționar care păstrează doar „există” ar pierde unul dintre intervale.

find caută cheia fără să creeze o intrare nouă; end() semnalează absența. Câmpul second al perechii găsite este frecvența. Actualizarea cu paranteze drepte creează frecvența inițială zero când cheia apare pentru prima dată.

Folosind map, fiecare căutare și actualizare are cost logaritmic în numărul cheilor. Timpul total este O(n log(n+1)), iar memoria O(n). Nu îl prezentăm ca timp liniar, deoarece reprezentarea aleasă are acest cost de căutare.

Exersează

1 -1 1 cu k=1 dă 3, 0 0 cu k=0 dă 3, iar vectorul gol dă 0. Pentru 2 -2 2 -2, cu k=0, răspunsul este 4. Listează intervalele înainte de verificarea cu programul.

Revezi sumele prefix, dicționarele map și complexitatea.

Întrebări frecvente

Cum număr secvențele cu suma k folosind sume prefix?

Pentru suma prefix curentă p, numără prefixele anterioare cu valoarea p-k. Fiecare astfel de prefix delimitează o secvență care se termină în poziția curentă și are suma k.

De ce inițializez frecvența sumei zero cu 1?

Ea reprezintă prefixul gol. Astfel sunt numărate și secvențele care încep de la primul element. Fără această inițializare, aceste soluții pot lipsi.

Funcționează metoda sumelor prefix și cu numere negative?

Da. Relația dintre două prefixe rămâne validă indiferent de semnul elementelor. Spre deosebire de unele ferestre glisante, metoda nu presupune că suma crește când extinzi intervalul.