Найти число подмассивов с нулевой суммой в O (n)

Question

Это подзадача общей двухмерной задачи, которую я пытаюсь решить, сводя вышеупомянутую одномерную проблему. Вышеупомянутая проблема может быть легко решена, используя грубую силу в O (n ^ 2) время. Приведенное ниже решение пытается сделать за O (n) время. Подход заключается в следующем:

      Goal : sum(i,j)==0
      sum(i,j) = sum(0,j) - sum(0,i);
      sum(i,j) = 0 => sum(0,j) == sum(0,i)

Алгоритм вычисляет совокупную сумму и использует hashmap (unordered_map в c ++), чтобы найти количество равных сумм. Это с помощью

      [ preSum(sum)*(presum(sum)-1) ]/2;

Другой Пограничный случай, когда элемент равен нулю в массиве, число увеличивается, потому что элемент также будет подмассивом. Приведенное ниже решение обрывается в одном случае. Я не могу определить случай / край, в котором разбивается приведенный ниже код.

      int findCount(vector<int> temp){
         int m = temp.size();
         unordered_map<int,int> preSum;
         int count = 0;
         int sum = 0;
         for(int i = 0; i < m;i++){
            sum+=temp[i];
            if(temp[i]==0){
                count++;
            }else if(sum==0){
                count++;

            }
            if(preSum.find(sum)!=preSum.end()){
             preSum[sum]+=1;
            }else{

            preSum[sum] = 1;
            }
         }
       for(auto x : preSum){
            if(x.second > 1 )
                count+= (x.second * (x.second-1))/2;

       }
       return count;
     }

Answer 1

Ваш подход:

  Goal : sum(i,j)==0
  sum(i,j) = sum(0,j) - sum(0,i);
  sum(i,j) = 0 => sum(0,j) == sum(0,i)

предполагает, что i и j являются позициями между элементами. Они варьируются от 0 до length, НЕ от 0 до length-1. С этой интерпретацией вышеприведенное абсолютно точно и не требует «крайних случаев».

Ваш код, по-видимому, предполагает, что i и j являются включающими индексами элементов, которые варьируются от 0 до length-1.

В этом случае:

   sum(i,j) = sum(0,j) - sum(0,i-1)  //assume sum(0,-1) = 0
   sum(i,j) = 0 => sum(0,j) = sum(0,i-1)  if i>0 or
                   sum(0,j) = 0 if i=0

Это требует отдельного подсчета ситуаций, в которых i=0

Ни в коем случае вам не требуется специальная обработка 0 elements.

Answer 2

Подход :

В качестве общего подхода к проблемам, связанным с подмассивами, вы должны использовать суммы префиксов для добавления каждого подмассива.

Let p содержат наши суммы префиксов , и пусть nums будет заданным массивом.

Пусть p[i+1] = nums[0] + nums[1] + ... + nums[i] (длина p = длина nums + 1).

Тогда каждый подмассив можно записать как p[i-1] - p[i]. Таким образом, мы можем иметь p[i-1] - p[i] == 0 или нет.

Алгоритм :

Отказ от ответственности: 0 действительно являются подмассивами. Однако, если вы не хотите считать их, вы должны удалить их из входного массива, прежде чем делать следующее. Я не удалил 0.

Создайте массив p, содержащий префиксных сумм и посчитайте все p[i] == 0.

Однако имейте в виду, что подсчет c будет выполнен с учетом наличия c*num значений p[i] == 0. Тогда есть sum(c*(c-1)/2) возможных подмассивов.

Мое решение в Python 3.6+ и может быть использовано в качестве чертежа для вас.

'''
Time Complexity: O(N), where N is the length of nums
Space Complexity: O(N)
'''
from collections import Counter

def zeroSumSub(nums):
    if not nums:
      return -1

    p = [0]
    for num in nums:
        p.append(p[-1] + num)

    count = Counter(p)
    return sum(v*(v-1)//2 for v in count.values())

Если вас не устраивает Python:

p[-1] похоже на p[len(nums)-1] (таким образом, возвращает последний элемент массива).

Counter - неупорядоченная коллекция, элементы которой хранятся в виде ключей dict ( суммы префиксов ) и их количество как значение dict (количество c). В двух словах, он считает ha sh -табильные объекты.

// - целочисленное деление.