如何在O(n)中得到数组的平衡指数？

Question

我在C++中做了一个测试,要求一个函数返回一个索引,它将输入向量分成两部分,具有相同的元素总和,例如:对于vec = {1, 2, 3, 5, 4, -1, 1, 1, 2, -1},它可能返回3,因为1 + 2 + 3 = 6 = 4-1 + 1 + 1 + 2-1.所以我完成了返回正确答案的函数:

int func(const std::vector< int >& vecIn)
{
   for (std::size_t p = 0; p < vecin.size(); p++)
   {
      if (std::accumulator(vecIn.begin(), vecIn.begin() + p, 0) == 
          std::accumulator(vecIn.begin() + p + 1, vecIn.end(), 0))
             return p;
   }
   return -1;
}

我的问题是当输入是一个只包含1(或-1)的非常长的向量时,函数的返回很慢.所以我想到从中间开始搜索想要的索引,然后左右移动.但我认为最好的方法是索引处于合并排序算法顺序,即:n/2,n/4,3n/4,n/8,3n/8,5n/8,7n/8 ...其中n是向量的大小.有没有办法在公式中写这个顺序,所以我可以在我的函数中应用它？

谢谢

---

编辑 经过一些评论我不得不提到我几天前已经完成了测试,所以我忘了提及没有解决方案的部分:它应该返回-1 ...我已经更新了问题标题.

Answer 1

专门针对这个问题,我会使用以下算法:

1. 计算向量的总和.这给出了两个总和(空向量和全向量)
2. 对于每个元素按顺序,将一个元素从full移动到空,这意味着将sum(full)中的next元素的值添加到sum(empty).当两个总和相等时,您已找到索引.

这给出了ao(n)算法而不是o(n2)