C++ 数组的平衡索引

一个序列的平衡点索引是指序列中的一个索引，使得其左侧所有元素的总和等于其右侧所有元素的总和。

例如，在序列 A 中：

A{0}=-8

A{1}=2

A{2}=5

A{3}=2

A{4}=-6

A{5}=3

A{6}=0

3 是平衡点索引。A{0}+A{1}+A{2}=A{4}+A{5}+A{6}

7 不是平衡点，因为它不在范围内。

换句话说，一个数组的平衡点索引是一个索引 i，使得索引小于 i 的元素的总和等于索引大于 i 的元素的总和。我们知道索引 i 处的组件不包含在任何一部分中，并且规定如果存在多个平衡点索引，您必须返回第一个。如果找不到平衡点索引，则返回 -1。

方法 1：使用两个循环

在此方法中，我们使用两个循环，其中外层循环遍历所有元素，而内层循环确定外层循环选择的当前索引是否为平衡点索引。此解决方案的时间复杂度为 O(N^2)。此方法的目的是为每个索引找到所有事件的总和。外层循环遍历值数组，内层循环确定它是否包含平衡点索引。

步骤序列

• 使用两个循环。
• 代码的外层循环遍历所有元素，而内层循环确定外层循环选择的当前索引是否为平衡点索引。
• 遍历数组。
• 对于每个索引，找到当前索引两侧组件的总和。
• 如果 left_sum 和 right_sum 相等，则当前索引是平衡点索引。
• 否则，返回 -1。
• 此解决方案具有 O(n^2) 的时间复杂度。

文件名：Equilibrium_index.cpp

输出

6

方法 2：（巧妙且高效）

计算数组的总和并将数组的左侧和初始化为 0。遍历数组时，从总和中减去当前元素以获得正确的和。在每一步，仔细检查 left 和 right 和。如果两者相等，则返回当前索引。

第一个目标是获取数组的总和。之后，遍历数组并更新左侧和值。我们可以通过单独减去项来在循环中获得正确的和。存储数组的前缀和。前缀和可以帮助跟踪数组中直到任何索引的每个元素的和。现在，我们需要弄清楚如何跟踪当前索引值右侧的值的总和。

我们可以使用一个临时和变量，该变量最初保存数组元素的总和。如果我们从索引中删除当前值，我们就可以得到右侧的总值。现在，评估 left_sum 和 right_sum 值，以确定当前索引是否对应于平衡点索引。

算法

• 将 left_sum 设置为零。
• 计算整个数组的和作为总和
• 遍历数组，对每个索引 i 执行以下操作：
  1. 更新总和以获得正确的和。

1. sum = sum - array[i]
2. // 总和现在是准确的和
   1. 如果 left_sum 等于 sum，则返回当前索引。
3. // 为下一次迭代重新计算 left_sum。
   1. left_sum = array[i] + left_sum

• 返回 -1 // 如果我们退出循环而没有返回，则不会有平衡点索引。

文件名：EqIndex.cpp

输出

The First equilibrium index of the array is 6

方法 3

这是一个非常简单的方法。目标是将数组的前缀和乘以二。一次从数组的前端开始，另一次从数组的后端开始。

收集两个前缀和后，执行一个循环，并查看一个数组的两个前缀和是否与另一个数组的相应前缀和在至少一个索引 'i' 处相同。如果满足此条件，则此点可能被视为平衡点。

文件名：Equindex.cpp

输出

The First Point of equilibrium of the array is at index 6 

复杂度

时间复杂度：O(N)

空间复杂度：O(N)