Programa Javascript 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). 

<script>
// JavaScript Program to find equilibrium
// index of an array
function equilibrium(arr, n)
{
         var i, j;
         var 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(let j = 0; j < i; j++)
              leftsum += arr[j];
                
              /*get right sum*/
              rightsum = 0;
              for(let 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
       
     var arr = new Array(-7,1,5,2,-4,3,0);
     n = arr.length;
      document.write(equilibrium(arr,n));
        
// This code is contributed by simranarora5sos  
</script>

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: 

<script>
// program to find equilibrium
// index of an array
 function equilibrium(arr, n)
{
    sum = 0; // initialize sum of whole array
    leftsum = 0; // initialize leftsum
   
    /* Find sum of the whole array */
    for (let i = 0; i < n; ++i)
        sum += arr[i];
   
    for (let 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
  
arr =new Array(-7, 1, 5, 2, -4, 3, 0);
n=arr.length;
document.write("First equilibrium index is " + equilibrium(arr, n));
  
// This code is contributed by simranarora5sos
</script>

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.

<script>
// Program to find equilibrium index of an array
 function equilibrium(a, n)
{
    if (n == 1)
        return (0);
    var forward = new Array(0);
    var rev = new Array(0);
   
    // Taking the prefixsum from front end array
    for (let i = 0; i < n; i++) {
        if (i) {
            forward[i] = forward[i - 1] + a[i];
        }
        else {
            forward[i] = a[i];
        }
    }
   
    // Taking the prefixsum from back end of array
    for (let i = n - 1; i > 0; i--) {
        if (i <= n - 2) {
            rev[i] = rev[i + 1] + a[i];
        }
        else {
            rev[i] = a[i];
        }
    }
   
    // Checking if forward prefix sum
    // is equal to rev prefix
    // sum
    for (let i = 0; i < n; i++) {
        if (forward[i] == rev[i]) {
            return i;
        }
    }
    return -1;
   
    // If You want all the points
    // of equilibrium create
    // vector and push all equilibrium
    // points in it and
    // return the vector
}
   
// Driver code
    arr = new Array(-7, 1, 5, 2, -4, 3, 0);
    n = arr.length;
    document.write("First Point of equilibrium is at index "
         + equilibrium(arr, n) + "
");
           
// This code is contributed by simranarora5sos
</script>

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.