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)。