arrays - 在 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(c++ 中的 unordered_map)来查找相等和的数量。这是通过使用

      [ 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 元素进行特殊处理。