Java 给定零索引数组 & 该数组的均衡索引

A zero-indexed array given & An equilibrium index of this array

提问by Sirat Binte Siddique

A zero-indexed array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e. A[0] + A[1] + ... + A[P?1] = A[P+1] + ... + A[N?2] + A[N?1]. Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N?1.

给出了一个由 N 个整数组成的零索引数组 A。该数组的均衡索引是任何整数 P 使得 0 ≤ P < N 并且较低索引的元素总和等于较高索引元素的总和，即 A[0] + A[1] + ... + A[P?1] = A[P+1] + ... + A[N?2] + A[N?1]。假设零元素之和等于 0。如果 P = 0 或 P = N?1，就会发生这种情况。

For example, consider the following array A consisting of N = 8 elements:

例如，考虑以下由 N = 8 个元素组成的数组 A：

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

P = 1 is an equilibrium index of this array, because:

P = 1 是该数组的均衡指数，因为：

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

P = 3 is an equilibrium index of this array, because:

P = 3 是这个数组的均衡指数，因为：

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

P = 7 is also an equilibrium index, because:

P = 7 也是一个均衡指数，因为：

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

and there are no elements with indices greater than 7.

并且没有索引大于 7 的元素。

P = 8 is not an equilibrium index, because it does not fulfill the condition 0 ≤ P < N.

P = 8 不是均衡指标，因为它不满足条件 0 ≤ P < N。

Now i have to write a function:

现在我必须写一个函数：

int solution(int A[], int N);

that, given a zero-indexed array A consisting of N integers, returns any of its equilibrium indices. The function should return ?1 if no equilibrium index exists.

给定一个由 N 个整数组成的零索引数组 A，返回它的任何均衡索引。如果不存在均衡指数，该函数应返回 ?1。

For example, given array A shown above, the function may return 1, 3 or 7, as explained above.

例如，给定上面显示的数组 A，该函数可能返回 1、3 或 7，如上所述。

Assume that:

假使，假设：

N is an integer within the range [0..100,000];
each element of array A is an integer within the range [?2,147,483,648..2,147,483,647].

here have some Complexity:

这里有一些复杂性：

Elements of input arrays can be modified.

采纳答案by Eko Bayu

100 Score in Javascript

Javascript 100 分

function solution(V) {

    var sum = 0;
    for (i=0; i < V.length; i++) {
      sum += V[i];   
    }

    var leftSum= 0;
    var rightSum = 0;

    for (j=0; j < V.length; j++) {
      rightSum = sum - (leftSum + V[j]);
      if(leftSum == rightSum) {
          return j;
      }
      leftSum += V[j];
    }
    return -1;
}

回答by Kanga_Roo

In C++ (because that was one of the original tags, though it looks like it has been removed...)

在 C++ 中（因为这是原始标签之一，尽管它看起来已被删除......）

int solution(int a[], int N){
    int left;
    int right;
    for(int i = 0; i < N; i++){
        left  = 0;
        right = 0;
        for(int t = 0; t < N; t++){
            if(t < i)      left  += a[t];
            else if(t > i) right += a[t];
            else continue;
        }
        if(left == right) return i;
    }
    return -1;
}

...

int demo[] = {-1, 3, -4, 5, 1, -6, 2, 1};
cout << solution(demo,sizeof(demo)/sizeof(*demo));

if you want to see all the indices...

如果您想查看所有索引...

if(left == right) cout << "Equilibrium Index: " <<  i << endl;

I find it odd it doesn't need to return an array of indices; that said, should you need it that's not too hard to implement with some slight modification

我觉得很奇怪，它不需要返回索引数组；也就是说，如果您需要它，只需稍加修改即可实现

回答by Vlad from Moscow

The straightforward approach looks the following way.

直截了当的方法如下所示。

First of all you need to calculate the sum of all elements of the array

首先你需要计算数组所有元素的总和

For example if you have the array in C++

例如，如果您在 C++ 中有数组

int a[] = { -1, 3, -4, 5, 1, -6, 2, 1 };

then you can use an ordinary loop to calculate the sum or standard algorithm std::accumulatedeclared in header <numeric>

那么您可以使用普通循环来计算std::accumulate标题中声明的总和或标准算法<numeric>

For example

例如

long long int right_sum = 
    std::accumulate( std::begin( a ), std::end( a ), 0ll );

The sum of the elements of the left subsequence initially is equal to zero

左子序列的元素之和初始为零

long long int left_sum = 0;

Then you can apply standard algorithm std::find_ifwith an appropriate lambda-expression or again write an ordinary loop as for example

然后，您可以使用std::find_if适当的 lambda 表达式应用标准算法，或者再次编写一个普通循环，例如

for ( size_t i = 0; i < sizeof( a ) / sizeof( *a ); i++ )
{
    right_sum -= a[i];
    if ( left_sum == right_sum ) std::cout << i << ' ';
    left_sum += a[i];
}

The result will be

结果将是

1 3 7

回答by Hilary Brobbey

Dynamic programming approach. O(N) time. O(2N) space.

动态规划方法。准时。O(2N) 空间。

1. Keep two tables (arrays), tableBefore and tableAfter.
2. tableBefore has sum up to index i for every i; i -> 1 to N.
3. tableAfter has sum up to index i for every i; i -> N to 1.

4. Afterwards loops and compare every index in tableBefore and tableAfter. If it's equal, that's your equilibrium index.

   public static int EquilibriumIndex2(int[] a) {
   int len = a.length;
   int[] tableBefore = new int[len];
   int[] tableAfter = new int[len];
   
   tableBefore[0] = 0;
   for (int i = 1; i < len; i++) {
       tableBefore[i] = tableBefore[i - 1] + a[i - 1];
   }
   
   //System.out.println("tableBefore: " + Arrays.toString(tableBefore));
   tableAfter[len - 1] = 0;
   for (int i = len - 2; i >= 0; i--) {
       tableAfter[i] = tableAfter[i + 1] + a[i + 1];
   }
   //System.out.println("tableAfter: " + java.util.Arrays.toString(tableAfter));
   
   for (int j = 0; j < len; j++) {
       if (tableAfter[j] == tableBefore[j]) {
           return j;
       }
   }
   return -1;
   

   }

1. 保留两个表（数组），tableBefore 和 tableAfter。
2. tableBefore 对每个 i 求和到索引 i；我 -> 1 到 N。
3. tableAfter 对每个 i 求和索引 i；我 -> N 到 1。

4. Afterwards 循环并比较 tableBefore 和 tableAfter 中的每个索引。如果相等，那就是你的均衡指数。

   public static int EquilibriumIndex2(int[] a) {
   int len = a.length;
   int[] tableBefore = new int[len];
   int[] tableAfter = new int[len];
   
   tableBefore[0] = 0;
   for (int i = 1; i < len; i++) {
       tableBefore[i] = tableBefore[i - 1] + a[i - 1];
   }
   
   //System.out.println("tableBefore: " + Arrays.toString(tableBefore));
   tableAfter[len - 1] = 0;
   for (int i = len - 2; i >= 0; i--) {
       tableAfter[i] = tableAfter[i + 1] + a[i + 1];
   }
   //System.out.println("tableAfter: " + java.util.Arrays.toString(tableAfter));
   
   for (int j = 0; j < len; j++) {
       if (tableAfter[j] == tableBefore[j]) {
           return j;
       }
   }
   return -1;
   

   }

回答by Shayan C

You can use the sums approach to solve this. Whenever sum from left = sum from right, you have an equilibrium point.

您可以使用 sums 方法来解决这个问题。每当左侧总和 = 右侧总和时，您就有了一个平衡点。

public int solution(int[] A) {
    int[] sumLeft = new int[A.length];
    int[] sumRight = new int[A.length];

    sumLeft[0] = A[0];
    sumRight[A.length-1] = A[A.length-1];
    for (int i=1; i<A.length; i++){
        sumLeft[i] = A[i] + sumLeft[i-1];
    }
    for (int i=A.length-2; i>=0; i--) {
        sumRight[i] = sumRight[i+1] + A[i];
    }

    for (int i=0; i<A.length; i++) {
        if (sumLeft[i]==sumRight[i]) {
            return i;
        }
    }
    return -1;
}

回答by Bashir Momen

100% scored with c#

100% 用 c# 得分

using System;
class Solution {
    public int solution(int[] A) {
        // First calculate sum of complete array as `sum_right`
        long sum_right = 0;
        for (int i = 0; i < A.Length; i++)
        {
            sum_right += A[i];
        }

        // start calculating sum from left side (lower index) as `sum_left`
        // in each iteration subtract A[i] from complete array sum - `sum_right`
        long sum_left = 0;
        for (int p = 0; p < A.Length; p++)
        {
            sum_left += p - 1 < 0 ? 0: A[p-1];
            sum_right -= A[p];
            if (sum_left == sum_right)
            {
                 return p;
            }
        }
        return -1;


    }
}

回答by chris hu

The answer is posted in this blog: http://blog.codility.com/2011/03/solutions-for-task-equi.html. In order to avoid O(N^2) and achieve O(N) performance: The key observation for better running time is to update the left/right sums in constant time instead of recomputing them from the scratch.

答案发布在此博客中：http: //blog.codility.com/2011/03/solutions-for-task-equi.html。为了避免 O(N^2) 并实现 O(N) 性能：更好的运行时间的关键观察是在恒定时间内更新左/右和，而不是从头开始重新计算它们。

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; 
} 

回答by craftsmannadeem

Here is the java equivalent

这是java等价物

public static int equilibriumIndex(int[] array) {
    int INDEX_NOT_FOUND = -1;
    int rSum = 0, lSum = 0;

    for (int index = 0; index < array.length; index++) {
        rSum += array[index];           
    }

    for (int index = 0; index < array.length; index++) {
        lSum += (index==0) ? 0 : array[index -1];// cumulative sum before (left sum) the current index
        rSum -= array[index]; // sum after (right sum) the current index onwards
        if (lSum == rSum) { // if both sums, cumulative sum before the current index and cumulative sum after the current index is equal, we got the equilibrium index 
            return index;
        }                       
    }
    return INDEX_NOT_FOUND;
}

Here is how you would test it

这是您测试它的方法

@Test
public void equilibriumTest() {
    int result = ArrayUtils.equilibriumIndex(new int[]{1,2,3,1,6});
    assertThat(result, equalTo(3));
}

回答by Asiri Liyana Arachchi

100% - Java

100% - 爪哇

int solution(int A[], int N) {

    long sum = 0;
    for (int i = 0; i < A.length; i++) {
        sum += (long) A[i];
    }
    long leftSum = 0;
    long rightSum = 0;

    for (int i = 0; i < A.length; i++) {
        rightSum = sum - (leftSum + A[i]);
        if (leftSum == rightSum) {
            return i;
        }
        leftSum += A[i];
    }
    return -1;
}

}

}

回答by Matija

For the lazy ones and PHP developers:

对于懒惰的人和 PHP 开发人员：

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

echo solution($A) . "\n";

function solution($A)
{
    $sum = 0;

    for ($i=0; $i < count($A); $i++) {
        $sum += $A[$i];
    }

    $sumRight = 0;
    $sumLeft = 0;

    for ($j=0; $j < count($A); $j++) {
        $sumRight = $sum - ($sumLeft + $A[$j]);
        if ($sumLeft == $sumRight) {
            return $j;
        }
        $sumLeft += $A[$j];
    }
    return -1;
}

Complexity O(N)

复杂 O(N)