1. Overview

1.概述

In this tutorial, we’ll first learn the definition of the equilibrium indexes of an array. Subsequently, we’ll write a method to identify and locate them.

在本教程中，我们将首先学习数组的平衡索引的定义。随后，我们将编写一种方法来识别和定位它们。

2. Presentation of the Problem

2.问题的提出

Given a zero-indexed array A of size N, index i is an equilibrium index if the sum of the elements of lower indices is equal to the sum of the elements of higher indices. That is to say: A[0] + A[1] + … + A[i-1] = A[i+1] + A[i+2] + … + A[N-1]. In particular, for the first and last index of the array, the sum of the other elements should be 0. For example, let’s consider the array {1, -3, 0, 4, -5, 4, 0, 1, -2, -1}:

给定一个大小为N的零索引数组A，如果低索引元素之和等于高索引元素之和，则索引i为平衡索引：也就是说：A[0] + A[1] + … + A[i-1] = A[i+1] + A[i+2] + … + A[N-1]。例如，我们来看看数组 {1，-3，0，4，-5，4，0，1，-2，-1}：

1 is an equilibrium index because A[0] = 1 and A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8] + A[9] = 0 + 4 + (-5) + 4 + 0 + 1 + (-2) + (-1) = 1
4 is also an equilibrium index since A[0] + A[1] + A[2] + A[3] = 1 + (-3) + 0 + 4 = 2 and A[5] + A[6] + A[7] + A[8] + A[9] = 4 + 0 + 1 + (-2) + (-1) = 2
A[0] + A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8] = 1 + (-3) + 0 + 4 + (-5) + 4 + 0 + 1 + (-2) = 0 and there is no element with an index greater than 9, so 9 is an equilibrium index for this array, too
On the other hand, 5 isn’t an equilibrium index because A[0] + A[1] + A[2] + A[3] + A[4] = 1 + (-3) + 0 + 4 + (-5) = -3, whereas A[6] + A[7] + A[8] + A[9] = 0 + 1 + (-2) + (-1) = -2

3. Algorithm

3.算法

Let’s think about how to find the equilibrium indexes of an array. The first solution that might come to mind is to iterate over all elements and then compute both sums. However, this would entail an inner iteration on the array elements, which would hurt the performance of our algorithm.

让我们思考一下如何找到数组的平衡索引。第一个可能想到的解决方案是遍历所有元素，然后计算两个和。但是，这需要对数组元素进行内部迭代，这将损害我们算法的性能。

As a result, we’ll preferably start with computing all partial sums of the array. The partial sum at index i is the sum of all the elements of A with indexes lower or equal to i. We can do this in one unique iteration over the initial array. Then, we’ll notice that we can obtain the two sums we need thanks to the partial sums array:

因此，我们最好从计算数组的所有部分和开始。索引i处的部分和是索引小于或等于i的A中所有元素的和。我们可以在初始数组上进行一次唯一的迭代。然后，我们会注意到，由于部分求和数组的存在，我们可以得到所需的两个和：

Find the sum of the lower indices elements at index i-1 of the partial sum array; otherwise, it’s 0 if i=0
The sum of the higher indexes element is equal to the total sum of the array minus the sum of all array elements until index i, or in mathematical terms: A[i+1] + A[i+2] + … + A[N-1] = A[0] + A[1] + … + A[i-1] + A[i] + A[i+1] + … + A[N-1] – (A[0] + A[1] + … + A[i]). The total sum of the array is the value of the partial sum array at index N-1, and the second sum is the value of the partial sum array at index i

Afterward, we’ll simply iterate over the array and add the elements to the equilibrium index list if both expressions are equal. Hence, the complexity of our algorithm is O(N).

之后，我们只需遍历数组，如果两个表达式相等，则将元素添加到平衡索引列表中。因此，我们算法的复杂度为 O(N)。

4. Computing Partial Sums

4.计算部分和

In addition to the partial sums, 0 is the sum of the elements of A before index 0. Besides, 0 is the natural starting point for accumulating the sum. Thus, it looks convenient to add one element at the beginning of our partial sum array with the value 0:

除了部分和之外，0 是索引 0 之前的 A 元素之和。此外，0 是累加和的自然起点。因此，在部分和数组的开头添加一个值为 0 的元素看起来很方便：

int[] partialSums = new int[array.length + 1];
partialSums[0] = 0;
for (int i=0; i<array.length; i++) {
    partialSums[i+1] = partialSums[i] + array[i]; 
}

In a nutshell, in our implementation, the partial sum array contains the sum A[0] + A[1] + … + A[i] at index i+1. In other words, the i^th value of our partial sum array equals the sum of all elements of A with indices lower than i.

简而言之，在我们的实现中，部分求和数组包含索引 i+1 处的 A[0] + A[1] + … + A[i] 的和。换句话说，部分和数组的 i^th 值等于索引小于 i 的 A 中所有元素的和。

5. Listing All Equilibrium Indexes

5.列出所有均衡指数

We can now iterate over our initial array and decide if a given index is an equilibrium:

我们现在可以遍历我们的初始数组，并判断给定索引是否是一个均衡点：

List<Integer> equilibriumIndexes = new ArrayList<Integer>();
for (int i=0; i<array.length; i++) {
    if (partialSums[i] == (partialSums[array.length] - (partialSums[i+1]))) {
        equilibriumIndexes.add(i);
    }
}

As we can see, we gathered all the items that meet the conditions in our result List.

我们可以看到，我们在结果 List 中收集了所有符合条件的项目。

Let’s look at our method as a whole:

让我们从整体上看看我们的方法：

List<Integer> findEquilibriumIndexes(int[] array) {
    int[] partialSums = new int[array.length + 1];
    partialSums[0] = 0;
    for (int i=0; i<array.length; i++) {
        partialSums[i+1] = partialSums[i] + array[i]; 
    }
        
    List<Integer> equilibriumIndexes = new ArrayList<Integer>();
    for (int i=0; i<array.length; i++) {
        if (partialSums[i] == (partialSums[array.length] - (partialSums[i+1]))) {
            equilibriumIndexes.add(i);
        }
    }
    return equilibriumIndexes;
}

As we named our class EquilibriumIndexFinder, we can now unit test our method on our example array:

由于我们将类命名为 EquilibriumIndexFinder，因此现在可以在示例数组上对我们的方法进行单元测试：

@Test
void givenArrayHasEquilibriumIndexes_whenFindEquilibriumIndexes_thenListAllEquilibriumIndexes() {
    int[] array = {1, -3, 0, 4, -5, 4, 0, 1, -2, -1};
    assertThat(new EquilibriumIndexFinder().findEquilibriumIndexes(array)).containsExactly(1, 4, 9);
}

We used AssertJ to check that the output List contains the correct indexes: Our method behaves as expected!

我们使用 AssertJ 来检查输出 List 是否包含正确的索引：我们的方法与预期的一样！

6. Conclusion

6.结论

In this article, we designed and implemented an algorithm to find all the equilibrium indexes of a Java array. The data structure doesn’t have to be an array. It could also be a List or any ordered sequence of integers.

在本文中，我们设计并实现了一种算法，用于查找 Java 数组的所有平衡索引。数据结构不一定是数组。它也可以是一个 List 或任何有序的整数序列。

As always, the code is available over on GitHub.

与往常一样，代码可在 GitHub 上获取。