Equilibrium Index of an Array in Java

在本节中，我们将学习 数组的平衡索引是什么 以及如何通过 Java 程序找到平衡索引。

平衡索引

如果低于索引元素的总和等于高于索引元素的总和，则称为 数组 的平衡索引。

例如，考虑数组 [-7, 1, 5, 2, -4, 3, 0]，其中

a[0]=-7, a[1]=1, a[2]=5, a[3]=2, a[4]=-4, a[5]=3, a[6]=0

让我们找出平衡索引。根据定义

较低索引处的元素总和 = a[0]+a[1]+a[2] = -7+1+5 = -1

较高索引处的元素总和 = a[4]+a[5]+a[6] = -4+3+0 = -1

我们观察到较低索引处的元素总和等于较高索引处的元素总和。因此，对于给定的数组，平衡索引是 3。

在上面的数组中，6 也是一个平衡索引，因为 a[0] 到 a[5] 的总和为 0，而索引 a[6] 的值为 0。

查找平衡索引的方法

有三种方法可以找到数组的平衡索引

• 暴力破解法
• 使用迭代方法
• 使用增量方法

暴力破解法

在此方法中，我们使用两个循环。外层循环遍历数组，内层循环检查是否存在平衡索引。该思想是为每个索引范围查找元素的总和，并观察是否存在平衡索引。它需要 O(n²) 的时间和 O(1) 的空间复杂度来解决问题。

算法步骤

1. 遍历数组中的一个循环。
2. 对于每个索引，计算当前索引左侧和右侧的元素总和。
3. 如果 lsum 和 rsum 相等，则当前索引是平衡索引。
4. 否则，返回 -1。

让我们在 Java 程序中实现上述逻辑。

EquilibriumIndexExample1.java

输出

Equilibrium Index is: 3

在上述方法中，我们使用了嵌套循环来计算 i 的每个值的左侧和右侧总和。它执行 n(n-1) 次求和操作。

使用迭代方法

该方法使用了一些额外的空间。在此方法中，我们存储了数组的前缀和。它跟踪数组中任何索引之前的所有元素的总和。现在，我们需要跟踪当前索引右侧的值的总和。

要找到当前索引右侧的值的总和，请减去当前索引处的值。现在比较 lsum 和 rsum，如果它们相等，则当前索引是平衡索引。

算法步骤

• 使用一些额外的空间存储数组的前缀和。
• 查找数组的总和，并将其存储为右侧总和 (rsum)。
• 遍历数组并比较 rsum 和 lsum。
• 如果 rsum 和 lsum 相等，则返回 i（当前索引）。
• 否则，返回 -1。

它的时间和空间复杂度分别为 O(n)。让我们在 Java 程序中实现上述算法。

EquilibriumIndexExample2.java

输出

Equilibrium Index is: 5

使用增量方法

增量方法与迭代方法相同，只是有一些不同之处。该方法与之前的方法（迭代方法）的区别在于我们不需要存储前缀和。相反，我们在遍历数组的同时跟踪左侧总和。在此方法中，我们首先计算数组的总和。为了获得右侧总和，在循环中，我们逐个减去元素。它的时间和空间复杂度分别为 O(n) 和 O(1)。

算法步骤

• 将数组的总和存储在 tsum 变量中。
• 遍历数组，通过添加当前索引 (i) 处的值来跟踪 lsum，并通过从 tsum 中减去当前索引处的值来跟踪 rsum。
• 如果 lsum 和 rsum 相等，则返回当前索引 (i)。
• 否则，返回 -1。

让我们在 Java 程序中实现上述方法。

EquilibriumIndexExample3.java

输出 1

Equilibrium Index is: 4

输出 2

Equilibrium Index is: -1