C++程序数组平衡点的程序

编写一个函数 int equilibrium(int[] arr, int n) ，它会给定大小为n的序列arr[]，返回一个平衡点的索引（如果存在），否则返回-1。数组的平衡点是这样一个索引，使得较低的索引处的元素的总和等于较高的索引处元素的总和。例如，在一个数组A中：

示例：

输入 : A[] = {-7, 1, 5, 2, -4, 3, 0}

输出 : 3

3是平衡点，因为：

A[0] + A[1] + A[2] = A[4] + A[5] + A[6]

输入 : A[] = {1, 2, 3}

输出 : -1

方法1（简单但效率低）

使用两个循环。外部循环遍历所有元素，内部循环可以找出外部循环选择的当前索引是否是平衡点或者不是。

// C++ program to find equilibrium
// index of an array
#include <bits/stdc++.h>
using namespace std;

int equilibrium(int arr[], int n)
{
    int i, j;
    int leftsum, rightsum;

    /* Check for indexes one by one until
    an equilibrium index is found */
    for (i = 0; i < n; ++i)
    {    

        /* get left sum */
        leftsum = 0;
        for (j = 0; j < i; j++)
            leftsum += arr[j];

        /* get right sum */
        rightsum = 0;
        for (j = i + 1; j < n; j++)
            rightsum += arr[j];

        /* if leftsum and rightsum 
        are same, then we are done */
        if (leftsum == rightsum)
            return i;
    }

    /* return -1 if no equilibrium
    index is found */
    return -1;
}

// Driver code
int main()
{
    int arr[] = { -7, 1, 5, 2, -4, 3, 0 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    cout << equilibrium(arr, arr_size);
    return 0;
}

// This code is contributed
// by Akanksha Rai(Abby_akku)

输出

时间复杂度： O(n^2)

辅助空间： O(1)

方法2（巧妙而高效）

首先获取整个数组的总和。然后遍历数组并保持初始化为零的左侧和。在循环中，可以通过逐个减去元素来得到右侧和。感谢Sambasiva提供了这个解决方案和代码。

1）初始化leftsum为0
2）将数组的总和作为sum
3）遍历数组，对于每个索引i，执行以下操作。
a) 更新sum以获得右部分和。
sum = sum- arr[i]
//现在sum是右部分和
b) 如果leftsum等于sum，则返回当前索引。
//更新leftsum以进行下一次迭代。
c) leftsum = leftsum + arr[i]
4）返回-1
// 如果没有找到平衡点则退出循环

下面是上述方法的实现：

这个图像展示了上述方法的详细运行过程：

C++程序数组平衡点的程序

下面是上述方法的实现:

// C++找到数组的平衡索引程序
//包含bits/stdc ++。h
使用namespace std;
 
int equilibrium(int arr []，int n)
{
    int sum = 0; //初始化整个数组的总和
    int leftsum = 0; //初始化leftsum
 
    / *找到整个数组的总和* /
    for（int i = 0; i 



**输出**
```cpp
第一个平衡指数是3
</code></pre>

<strong>时间复杂度：</strong> O（n）<br />
<strong>辅助空间：</strong> O（1）

<strong>方法3：</strong>

这是一种非常简单和直接的方法。这个想法是两次取数组的前缀和。一次从数组的前端，另一次从数组的后端。

在进行两个前缀和后，运行循环并检查某个i是否来自某个数组的两个前缀和等于另一数组的前缀和，那么可以将该点视为平衡点。

<pre><code class="language-cpp  line-numbers">// C ++程序查找数组的平衡指数
# include
使用命名空间std;
 
int equilibrium（int a []，int n）
{
    if（n == 1）
        返回（0）;
    int forward [n] = {0};
    int rev [n] = {0};
 
    //从前端数组中获取前缀和
    for（int i = 0; i  0; i--）{
        if（i <= n-2）{
            rev [i] = rev [i + 1] + a [i];
        }其他{
            rev [i] = a [i];
        }
    }
 
    //检查前缀和是否相等
    //总和
    for（int i = 0; i 



**输出**
```cpp
第一个平衡点位于索引3处

时间复杂度： O（N）

辅助空间： O（N）