JavaScript数组最大平衡和程序

---

给定数组的平衡和是指数组特定点或索引处的和，在此之后，子数组的总和等于从第0个索引到当前索引（包括当前索引）的子数组的总和。我们将看到JavaScript中不同方法的示例和代码实现。

问题介绍

给定一个数组，我们必须找到一个点，从该点开始，左侧元素（包括当前索引元素）的总和等于右侧元素（不包括当前索引元素）的总和。可能存在多个具有平衡和属性的索引，对于这些情况，我们必须返回最大和。

例如

The given array is: 2, 3, -1, 0, -1, 2, 3
In the above array, the maximum equilibrium sum is 4 which can be found at both indexes 2 and 3. 

我们将看到三种方法来查找最大平衡和。

朴素方法

在这种方法中，我们将使用嵌套for循环遍历数组：

// function to get the equilibrium sum
function equiSum(arr){

   // getting the length of the array 
   var n = arr.length 
   
   // initializing the answer 
   var ans = 0 
   
   // traversing over the array 
   for(var i =0; i<n; i++)    {
      var sum1 = 0;
      
      // getting sum upto the current index 
      for(var j =0; j<= i; j++)        {
         sum1 += arr[j]
      }
      var sum2 = 0;
      
      // getting sum of elements present after the current element 
      for(var j = i+1; j<n; j++) {
         sum2 += arr[j];
      }
      if(sum1 == sum2 && ans < sum1)        { 
         ans = sum1  
      }
   }
   console.log("The maximum equilibrium sum in the given array is: " + ans);
}

// defining the array 
arr = [2, 3, -1, 0, -1, 2, 3]
equiSum(arr)

时间和空间复杂度

上述代码的时间复杂度为O(N*N)，其中N是给定数组的大小，因为我们对每个迭代都遍历给定数组的每个元素。

上述代码的空间复杂度为O(1)，因为我们没有使用额外的空间。

前缀和后缀数组方法

在这种方法中，我们将维护后缀和前缀数组，并根据它们尝试找到答案。

示例

// function to get the equilibrium sum
function equiSum(arr){

   // getting the length of the array 
   var n = arr.length 
   
   // initializing the answer 
   var ans = 0 
   
   // traversing over the array to get the prefix sum 
   var preSum = new Array(n)
   preSum[0] = arr[0];
   for(var i =1; i<n; i++) {
      preSum[i] = preSum[i-1] + arr[i];
   }
   var sufSum = new Array(n)
   sufSum[0] = arr[n-1];
   for(var i = n-2; i>=0;i--){
      sufSum[n-i-1] = sufSum[n-i-2] + arr[i];
   }
   
   // traversing over the array 
   for(var i = 0; i<n-1; i++){
      if(preSum[i] == sufSum[n-i-2] && ans < preSum[i]){
         ans = preSum[i];
      }
   }
   console.log("The maximum equilibrium sum in the given array is: " + ans);
}

// defining the array 
arr = [2, 3, -1, 0, -1, 2, 3]
equiSum(arr)

时间和空间复杂度

上述代码的时间复杂度为O(N)，其中N是给定数组的大小，因为我们只遍历给定数组的每个元素三次。

上述代码的空间复杂度为O(N)，因为我们将前缀和和后缀和存储在大小为N的数组中。

高效方法

在这种方法中，我们将维护两个变量，并使用它们来获得所需答案。

// function to get the equilibrium sum
function equiSum(arr){

   // getting the length of the array 
   var n = arr.length 
   
   // initializing the answer 
   var ans = 0 
   
   // traversing over the array to get the total sum 
   var total_sum = 0
   for(var i =0; i<n; i++) {
      total_sum += arr[i]
   }
   
   // traversing over the array 
   var cur_sum = 0;
   for(var i = 0; i<n-1; i++) {
      cur_sum += arr[i];
      total_sum -= arr[i];
      if(cur_sum == total_sum && ans < cur_sum) {
         ans = cur_sum
      }
   }
   console.log("The maximum equilibrium sum in the given array is: " + ans);
}

// defining the array 
arr = [2, 3, -1, 0, -1, 2, 3]
equiSum(arr)

时间和空间复杂度

上述代码的时间复杂度为O(N)，其中N是给定数组的大小，因为我们只遍历给定数组的每个元素两次。

上述代码的空间复杂度为O(1)，因为我们没有使用任何额外的空间。

结论

在本教程中，我们实现了JavaScript中数组最大平衡和的程序。平衡和是左侧元素（包括当前索引元素）的总和，等于右侧元素（不包括当前索引元素）的总和。我们已经看到了三种方法及其时间和空间复杂度：朴素方法O(N*N) & O(1)，前缀和方法O(N) & O(N)，以及高效方法O(N) & O(1)。