c++ - 在数组中找到一个索引在它之前和之后给出一个总和？

Question

给定一个数组，我想找到一个索引，它前面的数字和它后面的数字给出相等的总和。

例如像这样的数组 [4,5,6,11,7,8]

输出是索引3，因为4+5+6 = 7+8

Answer 1

首先找到所有项目的总和，将其保存为sum，然后从数组的开头读取并汇总要到达的项目(sum - current index value)/2，如果没有得到这样的结果，则意味着没有这样的索引，如果你进入sum/2每个索引迭代，意味着相关索引是你的答案。

示例：4,5,6,11,7,8 总和 = 41。

check index 0: currentSum  = 4, currentSum - currentValue = 4-4 != (41 - 4)/2
check index 1: currentSum  =  9, currentSum - currentValue = 9-5 != (41 - 5)/2
check index 2: currentSum  = 15, currentSum - currentValue = 15-6 != (41 - 6)/2
check index 3: currentSum  = 26, currentSum - currentValue = 15 == (41 - 11)/2

Answer 2

创建（包含）前缀和数组（这需要 O(n) 步）

然后对于每个索引0 < i < n，检查是否prefixsum[i - 1] == prefixsum[n - 1] - prefixsum[i]，i如果返回true。（也需要 O(n) 步）。

---

您可以更轻松地执行此操作（并且空间更少）：

计算数组的总和。在）

然后，通过数组，跟踪前缀总和（这次不包括在内）。比较prefixsum == sum - (prefixsum + current)。如果为真，则返回当前索引。也是 O(n)。

本质上它与上面的相同，但避免将前缀和保存在数组中。

Answer 3

尝试构建范围和段树？检查每个节点，如果它们的左/右子节点相等，则返回它的索引。也许矫枉过正。