Programa Java para el índice de equilibrio de una array

El índice de equilibrio de una array es un índice tal que la suma de los elementos en los índices más bajos es igual a la suma de los elementos en los índices más altos. Por ejemplo, en una array A: 

Ejemplo : 

Entrada : A[] = {-7, 1, 5, 2, -4, 3, 0} 
Salida : 3 
3 es un índice de equilibrio, porque: 
A[0] + A[1] + A[2] = A [4] + A[5] + A[6]

Entrada : A[] = {1, 2, 3} 
Salida : -1 

Escribe una función int equilibrio(int[] arr, int n) ; que dada una secuencia arr[] de tamaño n, devuelve un índice de equilibrio (si lo hay) o -1 si no existen índices de equilibrio. 

Método 1 (Simple pero ineficiente) 
Use dos bucles. El bucle externo itera a través de todo el elemento y el bucle interno descubre si el índice actual elegido por el bucle externo es un índice de equilibrio o no. La complejidad temporal de esta solución es O(n^2). 

// Java program to find equilibrium
// index of an array
 
class EquilibriumIndex {
    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
    public static void main(String[] args)
    {
        EquilibriumIndex equi = new EquilibriumIndex();
        int arr[] = { -7, 1, 5, 2, -4, 3, 0 };
        int arr_size = arr.length;
        System.out.println(equi.equilibrium(arr, arr_size));
    }
}
 
// This code has been contributed by Mayank Jaiswal

3

Complejidad del tiempo: O(n^2)

Método 2 (complicado y eficiente) 
La idea es obtener primero la suma total de la array. Luego itere a través de la array y siga actualizando la suma izquierda que se inicializa como cero. En el ciclo, podemos obtener la suma correcta restando los elementos uno por uno. Gracias a Sambasiva por sugerir esta solución y proporcionar el código para esto.

1) Initialize leftsum  as 0
2) Get the total sum of the array as sum
3) Iterate through the array and for each index i, do following.
    a)  Update sum to get the right sum.  
           sum = sum - arr[i] 
       // sum is now right sum
    b) If leftsum is equal to sum, then return current index. 
       // update leftsum for next iteration.
    c) leftsum = leftsum + arr[i]
4) return -1 
// If we come out of loop without returning then
// there is no equilibrium index

La siguiente imagen muestra la ejecución en seco del enfoque anterior: 

A continuación se muestra la implementación del enfoque anterior: 

// Java program to find equilibrium
// index of an array
 
class EquilibriumIndex {
    int equilibrium(int arr[], int n)
    {
        int sum = 0; // initialize sum of whole array
        int leftsum = 0; // initialize leftsum
 
        /* Find sum of the whole array */
        for (int i = 0; i < n; ++i)
            sum += arr[i];
 
        for (int i = 0; i < n; ++i) {
            sum -= arr[i]; // sum is now right sum for index i
 
            if (leftsum == sum)
                return i;
 
            leftsum += arr[i];
        }
 
        /* If no equilibrium index found, then return 0 */
        return -1;
    }
 
   // Driver code
    public static void main(String[] args)
    {
        EquilibriumIndex equi = new EquilibriumIndex();
        int arr[] = { -7, 1, 5, 2, -4, 3, 0 };
        int arr_size = arr.length;
        System.out.println("First equilibrium index is " +
                          equi.equilibrium(arr, arr_size));
    }
}
 
// This code has been contributed by Mayank Jaiswal

First equilibrium index is 3

Salida: El 
primer índice de equilibrio es 3

Complejidad de tiempo: O(n)

Método 3:

Este es un método bastante simple y directo. La idea es tomar la suma del prefijo de la array dos veces. Una vez desde el extremo frontal de la array y otra desde la parte posterior de la array.

Después de tomar ambas sumas de prefijos, ejecute un ciclo y verifique si hay alguna i si la suma de prefijos de una array es igual a la suma de prefijos de la segunda array, entonces ese punto puede considerarse como el punto de equilibrio.

// Java program to find equilibrium
// index of an array
class GFG{
 
static int equilibrium(int a[], int n)
{
    if (n == 1)
        return (0);
     
    int[] front = new int[n];
    int[] back = new int[n];
 
    // Taking the prefixsum from front end array
    for (int i = 0; i < n; i++)
    {
        if (i != 0)
        {
            front[i] = front[i - 1] + a[i];
        }
        else
        {
            front[i] = a[i];
        }
    }
   
    // Taking the prefixsum from back end of array
    for (int i = n - 1; i > 0; i--)
    {
        if (i <= n - 2)
        {
            back[i] = back[i + 1] + a[i];
        }
        else
        {
            back[i] = a[i];
        }
    }
     
    // Checking for equilibrium index by
    //comparing front and back sums
    for(int i = 0; i < n; i++)
    {
        if (front[i] == back[i])
        {
            return i;
        }
    }
     
    // If no equilibrium index found,then return -1
    return -1;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { -7, 1, 5, 2, -4, 3, 0 };
    int arr_size = arr.length;
     
    System.out.println("First Point of equilibrium " +
                       "is at index " +
                       equilibrium(arr, arr_size));
}
}
 
// This code is contributed by Lovish Aggarwal

First Point of equilibrium is at index 3

Complejidad de tiempo: O(N)

Complejidad espacial: O(N)

Consulte el artículo completo sobre el índice de equilibrio de una array para obtener más detalles.