阵列的平衡指数

数组的平衡索引是这样一种索引,即较低索引的元素之和等于较高索引的元素之和。例如,在数组中:

null

例子:

输入 :A[]={-7,1,5,2,-4,3,0} 输出 : 3 3是一个平衡指数,因为: A[0]+A[1]+A[2]=A[4]+A[5]+A[6]

输入 :A[]={1,2,3} 输出 : -1

写一个函数 整数平衡(整数[]arr,整数n) ; 给定一个大小为n的序列arr[],返回一个平衡指数(如果有),如果不存在平衡指数,则返回-1。

方法1(简单但低效) 使用两个循环。外循环遍历所有元素,内循环找出外循环选择的当前索引是否为平衡索引。该解的时间复杂度为O(n^2)。

C++

// C++ program to find equilibrium
// index of an array
#include <bits/stdc++.h>
using namespace std;
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
int main()
{
int arr[] = { -7, 1, 5, 2, -4, 3, 0 };
int arr_size = sizeof (arr) / sizeof (arr[0]);
cout << equilibrium(arr, arr_size);
return 0;
}
// This code is contributed
// by Akanksha Rai(Abby_akku)


C

// C program to find equilibrium
// index of an array
#include <stdio.h>
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
int main()
{
int arr[] = { -7, 1, 5, 2, -4, 3, 0 };
int arr_size = sizeof (arr) / sizeof (arr[0]);
printf ( "%d" , equilibrium(arr, arr_size));
getchar ();
return 0;
}


JAVA

// 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


Python3

# Python program to find equilibrium
# index of an array
# function to find the equilibrium index
def equilibrium(arr):
leftsum = 0
rightsum = 0
n = len (arr)
# Check for indexes one by one
# until an equilibrium index is found
for i in range (n):
leftsum = 0
rightsum = 0
# get left sum
for j in range (i):
leftsum + = arr[j]
# get right sum
for j in range (i + 1 , n):
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
arr = [ - 7 , 1 , 5 , 2 , - 4 , 3 , 0 ]
print (equilibrium(arr))
# This code is contributed by Abhishek Sharama


C#

// C# program to find equilibrium
// index of an array
using System;
class GFG {
static 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) {
// initialize left sum
// for current index i
leftsum = 0;
// initialize right sum
// for current index i
rightsum = 0;
/* get left sum */
for (j = 0; j < i; j++)
leftsum += arr[j];
/* get right sum */
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()
{
int [] arr = { -7, 1, 5, 2, -4, 3, 0 };
int arr_size = arr.Length;
Console.Write(equilibrium(arr, arr_size));
}
}
// This code is contributed by Sam007


PHP

<?php
// PHP program to find equilibrium
// index of an array
function equilibrium( $arr , $n )
{
$i ; $j ;
$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
$arr = array ( -7, 1, 5, 2, -4, 3, 0 );
$arr_size = sizeof( $arr );
echo equilibrium( $arr , $arr_size );
// This code is contributed
// by akt_mit
?>


Javascript

<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

时间复杂性: O(n^2)

方法2(技巧和效率) 这个想法是先得到数组的总和。然后遍历数组并不断更新初始化为零的左和。在循环中,我们可以通过逐个减去元素得到正确的和。感谢Sambasiva提出这个解决方案并提供代码。

1) Initialize leftsum  as 02) Get the total sum of the array as sum3) 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

下图显示了上述方法的试运行:

图片[1]-阵列的平衡指数-yiteyi-C++库

以下是上述方法的实施情况:

C++

// C++ program to find equilibrium
// index of an array
#include <bits/stdc++.h>
using namespace std;
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
int main()
{
int arr[] = { -7, 1, 5, 2, -4, 3, 0 };
int arr_size = sizeof (arr) / sizeof (arr[0]);
cout << "First equilibrium index is " << equilibrium(arr, arr_size);
return 0;
}
// This is code is contributed by rathbhupendra


C

// C program to find equilibrium
// index of an array
#include <stdio.h>
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
int main()
{
int arr[] = { -7, 1, 5, 2, -4, 3, 0 };
int arr_size = sizeof (arr) / sizeof (arr[0]);
printf ( "First equilibrium index is %d" ,
equilibrium(arr, arr_size));
getchar ();
return 0;
}


JAVA

// 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


Python3

# Python program to find the equilibrium
# index of an array
# function to find the equilibrium index
def equilibrium(arr):
# finding the sum of whole array
total_sum = sum (arr)
leftsum = 0
for i, num in enumerate (arr):
# total_sum is now right sum
# for index i
total_sum - = num
if leftsum = = total_sum:
return i
leftsum + = num
# If no equilibrium index found,
# then return -1
return - 1
# Driver code
arr = [ - 7 , 1 , 5 , 2 , - 4 , 3 , 0 ]
print ( 'First equilibrium index is ' ,
equilibrium(arr))
# This code is contributed by Abhishek Sharma


C#

// C# program to find the equilibrium
// index of an array
using System;
class GFG {
static int equilibrium( int [] arr, int n)
{
// initialize sum of whole array
int sum = 0;
// initialize leftsum
int leftsum = 0;
/* Find sum of the whole array */
for ( int i = 0; i < n; ++i)
sum += arr[i];
for ( int i = 0; i < n; ++i) {
// sum is now right sum
// for index i
sum -= arr[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()
{
int [] arr = { -7, 1, 5, 2, -4, 3, 0 };
int arr_size = arr.Length;
Console.Write( "First equilibrium index is " +
equilibrium(arr, arr_size));
}
}
// This code is contributed by Sam007


PHP

<?php
// PHP 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 ( $i = 0; $i < $n ; ++ $i )
$sum += $arr [ $i ];
for ( $i = 0; $i < $n ; ++ $i )
{
// sum is now right sum
// for index i
$sum -= $arr [ $i ];
if ( $leftsum == $sum )
return $i ;
$leftsum += $arr [ $i ];
}
/* If no equilibrium index
found, then return 0 */
return -1;
}
// Driver code
$arr = array ( -7, 1, 5, 2, -4, 3, 0 );
$arr_size = sizeof( $arr );
echo "First equilibrium index is " ,
equilibrium( $arr , $arr_size );
// This code is contributed by ajit
?>


Javascript

<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

时间复杂性: O(n)

方法3:

这是一个非常简单直接的方法。其思想是将数组的前缀和取两次。一次从阵列前端,另一次从阵列后端。

在获取两个前缀和之后,运行一个循环并检查一些i,如果一个数组的前缀和等于第二个数组的前缀和,那么该点可以被视为平衡点。

C++

// C++ program to find equilibrium index of an array
#include <bits/stdc++.h>
using namespace std;
int equilibrium( int a[], int n)
{
if (n == 1)
return (0);
int forward[n] = { 0 };
int rev[n] = { 0 };
// Taking the prefixsum from front end array
for ( int 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 ( int 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 ( int 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
int main()
{
int arr[] = { -7, 1, 5, 2, -4, 3, 0 };
int n = sizeof (arr) / sizeof (arr[0]);
cout << "First Point of equilibrium is at index "
<< equilibrium(arr, n) << "" ;
return 0;
}


JAVA

// 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


Python3

# Python program to find the equilibrium
# index of an array
# Function to find the equilibrium index
def equilibrium(arr):
left_sum = []
right_sum = []
# Iterate from 0 to len(arr)
for i in range ( len (arr)):
# If i is not 0
if (i):
left_sum.append(left_sum[i - 1 ] + arr[i])
right_sum.append(right_sum[i - 1 ] + arr[ len (arr) - 1 - i])
else :
left_sum.append(arr[i])
right_sum.append(arr[ len (arr) - 1 ])
# Iterate from 0 to len(arr)
for i in range ( len (arr)):
if (left_sum[i] = = right_sum[ len (arr) - 1 - i ]):
return (i)
# If no equilibrium index found,then return -1
return - 1
# Driver code
arr = [ - 7 , 1 , 5 , 2 , - 4 , 3 , 0 ]
print ( 'First equilibrium index is ' ,
equilibrium(arr))
# This code is contributed by Lokesh Sharma


C#

// C# program to find equilibrium
// index of an array
using System;
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;
Console.WriteLine( "First Point of equilibrium " +
"is at index " +
equilibrium(arr, arr_size));
}
}
// This code is contributed by ukasp


Javascript

<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

时间复杂性: O(N)

空间复杂性: O(N)

方法4: –使用二进制搜索

为了处理所有的测试用例,我们可以使用二进制搜索算法。

1.计算中间值,然后围绕中间值创建左和右和

2.如果左和大于右和,向左移动,直到其等于或小于右和

3.否则,如果右和大于左,则向右移动,直到其等于或小于左和。

4.最后,我们比较两个和,如果它们相等,我们得到的中间值为指数-1

C++

#include <bits/stdc++.h>
using namespace std;
void find( int arr[], int n)
{
int mid = n / 2;
int leftSum = 0, rightSum = 0;
//calculation sum to left of mid
for ( int i = 0; i < mid; i++)
{
leftSum += arr[i];
}
//calculating sum to right of mid
for ( int i = n - 1; i > mid; i--)
{
rightSum += arr[i];
}
//if rightsum > leftsum
if (rightSum > leftSum)
{
//we keep moving right until rightSum become equal or less than leftSum
while (rightSum > leftSum && mid < n - 1)
{
rightSum -= arr[mid + 1];
leftSum += arr[mid];
mid++;
}
}
else
{
//we keep moving right until leftSum become equal or less than RightSum
while (leftSum > rightSum && mid > 0)
{
rightSum += arr[mid];
leftSum -= arr[mid - 1];
mid--;
}
}
//check if both sum become equal
if (rightSum == leftSum)
{
cout << "First Point of equilibrium is at index =" << mid << endl;
return ;
}
cout << "First Point of equilibrium is at index =" << -1 << endl;
}
int main()
{
int arr[] = { 1,1,1,-1,1,1,1 };
int n = sizeof (arr) / sizeof (arr[0]);
find(arr, n);
}


JAVA

// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
static void find( int arr[], int n)
{
int mid = n / 2 ;
int leftSum = 0 , rightSum = 0 ;
//calculation sum to left of mid
for ( int i = 0 ; i < mid; i++)
{
leftSum += arr[i];
}
//calculating sum to right of mid
for ( int i = n - 1 ; i > mid; i--)
{
rightSum += arr[i];
}
//if rightsum > leftsum
if (rightSum > leftSum)
{
//we keep moving right until rightSum become equal or less than leftSum
while (rightSum > leftSum && mid < n - 1 )
{
rightSum -= arr[mid + 1 ];
leftSum += arr[mid];
mid++;
}
}
else
{
//we keep moving right until leftSum become equal or less than RightSum
while (leftSum > rightSum && mid > 0 )
{
rightSum += arr[mid];
leftSum -= arr[mid - 1 ];
mid--;
}
}
//check if both sum become equal
if (rightSum == leftSum)
{
System.out.print( "First Point of equilibrium is at index =" + mid);
return ;
}
System.out.print( "First Point of equilibrium is at index =" + - 1 );
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1 , 1 , 1 ,- 1 , 1 , 1 , 1 };
int n = arr.length;
find(arr, n);
}
}


Python3

# Python program for the above approach
def find(arr, n):
mid = n / / 2 ;
leftSum = 0 ;
rightSum = 0 ;
# calculation sum to left of mid
for i in range (mid):
leftSum + = arr[i];
# calculating sum to right of mid
for i in range (n - 1 , mid, - 1 ):
rightSum + = arr[i];
# if rightsum > leftsum
if (rightSum > leftSum):
# we keep moving right until rightSum become equal or less than leftSum
while (rightSum > leftSum and mid < n - 1 ):
rightSum - = arr[mid + 1 ];
leftSum + = arr[mid];
mid + = 1 ;
else :
# we keep moving right until leftSum become equal or less than RightSum
while (leftSum > rightSum and mid > 0 ):
rightSum + = arr[mid];
leftSum - = arr[mid - 1 ];
mid - = 1 ;
# check if both sum become equal
if (rightSum = = leftSum):
print ( "First Point of equilibrium is at index =" , mid);
return ;
print ( "First Point of equilibrium is at index =" , - 1 );
# Driver code
if __name__ = = '__main__' :
arr = [ 1 , 1 , 1 , - 1 , 1 , 1 , 1 ];
n = len (arr);
find(arr, n);
# This code is contributed by gauravrajput1


C#

// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
public class GFG {
static void find( int [] arr, int n)
{
int mid = n / 2;
int leftSum = 0, rightSum = 0;
//calculation sum to left of mid
for ( int i = 0; i < mid; i++)
{
leftSum += arr[i];
}
//calculating sum to right of mid
for ( int i = n - 1; i > mid; i--)
{
rightSum += arr[i];
}
//if rightsum > leftsum
if (rightSum > leftSum)
{
//we keep moving right until rightSum become equal or less than leftSum
while (rightSum > leftSum && mid < n - 1)
{
rightSum -= arr[mid + 1];
leftSum += arr[mid];
mid++;
}
}
else
{
//we keep moving right until leftSum become equal or less than RightSum
while (leftSum > rightSum && mid > 0)
{
rightSum += arr[mid];
leftSum -= arr[mid - 1];
mid--;
}
}
//check if both sum become equal
if (rightSum == leftSum)
{
Console.Write( "First Point of equilibrium is at index =" + mid);
return ;
}
Console.Write( "First Point of equilibrium is at index =" + -1);
}
// Driver Code
public static void Main ( string [] args) {
int [] arr = { 1,1,1,-1,1,1,1 };
int n = arr.Length;
find(arr, n);
}
}
// This code is contributed by code_hunt.


Javascript

<script>
// javascript program for the above approach
function find(arr , n) {
var mid = parseInt(n / 2);
var leftSum = 0, rightSum = 0;
// calculation sum to left of mid
for (i = 0; i < mid; i++) {
leftSum += arr[i];
}
// calculating sum to right of mid
for (i = n - 1; i > mid; i--) {
rightSum += arr[i];
}
// if rightsum > leftsum
if (rightSum > leftSum)
{
// we keep moving right until rightSum
// become equal or less than leftSum
while (rightSum > leftSum && mid < n - 1) {
rightSum -= arr[mid + 1];
leftSum += arr[mid];
mid++;
}
}
else
{
// we keep moving right until leftSum
// become equal or less than RightSum
while (leftSum > rightSum && mid > 0) {
rightSum += arr[mid];
leftSum -= arr[mid - 1];
mid--;
}
}
// check if both sum become equal
if (rightSum == leftSum) {
document.write( "First Point of equilibrium is at index =" + mid);
return ;
}
document.write( "First Point of equilibrium is at index =" + -1);
}
// Driver code
var arr = [ 1, 1, 1, -1, 1, 1, 1 ];
var n = arr.length;
find(arr, n);
// This code is contributed by gauravrajput1
</script>


输出

First Point of equilibrium is at index =3

正如Sameer所指出的,我们可以删除return语句,并添加一个print语句来打印所有均衡索引,而不是只返回一个。

如果您发现上述代码/算法不正确,请写下评论,或者找到更好的方法来解决相同的问题。

© 版权声明
THE END
喜欢就支持一下吧
点赞14 分享