Вычислить сумму разрезов массива эффективным образом

Question

Запишите функцию: int countZeroSlices(int* arr);, которая возвращает количество срезов в массиве, сумма которых равна 0. Например: arr = {2, -2, 3, 0, 4, -7} ломтиками, которые удовлетворяют требованиям: (2, -2) (0), (3,4, -7), (2, -2,0,3,4, -7), поэтому функция должна возвращать «4» срезы.

Решение должно быть O(n.Log(n)), где п размер массива

Мой текущий код:

#include <iostream> 
#include <vector> 

using namespace std; 

int main() 
{ 
    vector<int> A{2,-2,0,3,4,-7}; 

    int sum=0; 
    int count=0; 
    for(size_t i=0; i<A.size(); i++) 
    { 
     sum += A[i]; 
     if(sum==0 || A[i] ==0) count++; 
    } 
    cout<<count; 


    return 0; 
} 

_ выход 3 который не является правильным ответом. Обратите внимание, что я обнаруживать все кусочки, за исключением средних единиц например: (3,4, -7)

Answer 1

#include <iostream> 
#include <map> 
#include <vector> 

using namespace std; 

int main() 
{ 
    vector<int> A{2,-2,3,0,4,-7}; 
    map<int, int> partial_sums; 
    partial_sums[0] = 1; 
    int sum = 0; 
    int count = 0; 
    for (size_t i = 0; i < A.size(); i++) { 
     sum += A[i]; 
     count += partial_sums[sum]; 
     partial_sums[sum]++; 
    } 
    cout << count; 
    return 0; 
} 

Пояснения: Каждый срез массива представляет собой разность между двумя частичными суммами. Например, 3 + 4 + (-7) = (2 + (-2) + 0 + 3 + 4 + (-7)) - (2 + (-2) + 0). Чтобы подсчитать количество срезов с нулевой суммой , заканчивающееся в позиции i, обратите внимание, что такой срез представляет собой разницу между частичной суммой, заканчивающейся в позиции i, и некоторой предыдущей частичной суммой. Предыдущая частичная сумма должна иметь одно и то же значение, чтобы результат был равен нулю. Используя std::map, получаем O (n log n).

Редактировать: Исправлена ​​ошибка. Начальная запись на карте необходима для учета пустой частичной суммы.