c# - 数组的平衡索引如何工作？

Question

我在 Codility 上尝试了一个演示测试，用于查找数组的平衡索引。我不确定测试是为了找到数组的平衡索引还是什么。我四处搜索，发现了以下示例:

The equilibrium index of a sequence is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. For example, in a sequence A:

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

3 is an equilibrium index, because:

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

6 is also an equilibrium index, because:

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

根据此信息，我看到测试数组包含 7 个元素。中间元素 A[3]=2 似乎被忽略了。是因为它在前3个元素和后3个元素之间吗？这个例子中的平衡指数 6 是如何得出的？

这是用来计算这个的方法:

int equi(int arr[], int n) {
    if (n==0) return -1; 
    long long sum = 0;
    int i; 
    for(i=0;i<n;i++) sum+=(long long) arr[i]; 

    long long sum_left = 0;    
    for(i=0;i<n;i++) {
        long long sum_right = sum - sum_left - (long long) arr[i];
        if (sum_left == sum_right) return i;
        sum_left += (long long) arr[i];
    } 
    return -1; 
}  

当我进行 Codility 演示测试时，我使用了方法(如下)和最初从 0 开始的 for 循环。我收到了 1 测试用例的“错误答案”消息, 5, 2, 1, 4, 0 并且 Codility 正在寻找结果 11。

我修改了方法中的两个 for 循环，并在 i = 1 开始第一个循环，在 i = 2 开始第二个循环直到它产生 11 的结果，Codility 对此感到满意。我基本上只是调整方法，直到 Codility 满意为止(我拍摄 11，因为 Codility 指定这是他们正在寻找的答案)，但我真的不知道为什么 Codility 很高兴或者我的调整有什么意义 -只是命中注定:

        ...
        int[] B = new int[] { 1, 5, 2, 1, 4, 0 };

        Console.WriteLine(solution3(B));
    }

    public int solution3(int[] A)
    {
        long rsum = 0;

        for (int i = 1; i < A.Count(); i++)
            rsum += A[i];

        long lsum = A[0];
        int min = (int)Math.Abs(lsum - rsum);
        
        for (int i = 2; i < A.Count() - 1; i++)
        {
            lsum += A[i];
            rsum -= A[i];
            int diff = (int)Math.Abs(lsum - rsum);
            if (diff >= min)
                min = diff;
        }

        return min;
    } 

为什么这种调整(命中与未命中)满足了 Codility 测试？什么是均衡指数？它是如何到达的？注意:如果步骤 A 和步骤 E 之间有步骤(我必须凭直觉判断步骤之间的步骤)，那么步骤 B、C 和 D 是什么？

Answer 1

什么是平衡指数，它是如何确定的？

将您的阵列想象成一 block 板上有不同大小的重物(负重可以被认为是附着在板上的氦气球)。每个重量从左到右编号。你的任务是在木板下方的任何编号位置放置一个支点，以使木板保持平衡。 (我们将棋盘本身视为失重，并假设重量与中心的距离无关紧要。)使棋盘平衡的位置是均衡指标。支点处的重量不“重要”，因为它不在任何一侧；它在中间。

这是第一个例子的图片:

这里，3是均衡指数，因为支点左边的权重之和等于支点右边的权重之和(-7 + 5 + 1 = -1 = -4 + 3 + 0).

这是第二个例子:

出于同样的原因，我们看到 6 也是一个均衡指数。支点左边的所有元素加起来为零。由于支点右侧没有元素，因此该和也为零。

找到平衡指标的基本算法是这样的:

1. 遍历数组并将所有元素相加。称此总和为总计。
2. 将变量 left_sum 初始化为零。
3. 将变量right_sum 初始化为total。
4. 现在再次遍历数组。对于每个数组项:
   1. 从 right_sum 中减去当前项的值。
   2. 比较 left_sum 和 right_sum。如果相等，则当前项的指标为均衡指标。
   3. 将当前项的值添加到left_sum。

这就是它的全部。现在有意义吗？

---

我的算法怎么了？

至于为什么“Codility 演示测试”期望包含元素 { 1, 5, 2, 1, 4, 0 } 的数组的结果为 11，我不能说。您从未在问题中说过演示问题实际上是什么。如果问题是在该数组中找到第一个平衡索引，那么答案是该数组没有。逐步完成上述算法，这里是每个数组索引的左右总和:

Index  Left  Right
-----  ----  -----
    0     0     12
    1     1      7
    2     6      5
    3     8      4
    4     9      0
    5    13      0

如您所见，不存在左和等于右和的索引。 11 的预期结果甚至没有任何意义，因为只有六个元素。所以如果这个数组有一个平衡索引，它必须在 0 到 5 之间(含)。所以我猜提出的问题一定是别的原因。在我开始猜测你的算法为什么正确或不正确之前，你必须在你的问题中包含问题陈述。