JavaScript 查找数组的平衡索引

平衡索引是指数组中元素左右两侧的和相等的位置。换句话说，对于大小为n的数组，平衡索引i满足以下条件：−

arr[0] + arr[1] + ... + arr[i-1] = arr[i+1] + arr[i+2] + ... + arr[n-1]

i是平衡指数，arr是输入数组。我们可以另外说这个数组通过平衡指数i分成了两部分，使得左部分和右部分的元素总和相等。

示例：

让我们考虑以下数组 –

A = [2, 4, -3, 0, -4, 6, 1]
In this sequence, the equilibrium index is 3 (element 0) because (2+4-3) = (-4+6+1).
It is also balanced with another equilibrium index 5 (element 6) because (2+4-3+0-4) = (1).

问题陈述

给定一个整数数组，找到数组的平衡点的索引。如果没有平衡点，返回-1。

示例

考虑一个整数数组 –

[3, 7, 1, 5, 10, 2, 7, 9]

该数组的平衡索引是4，因为索引前的元素和（3+7+1+5 = 16）等于索引后的元素和（2+7+9 = 18）。

方法1：使用循环

使用两个循环：外循环遍历所有元素，内循环确定外循环选择的当前索引是否为平衡索引。该方法的时间复杂度为O(n2)，稍后将解释。使用两个循环很简单。目标是找到每个索引范围的元素和，然后查看是否存在平衡索引。外循环遍历数组，内循环评估是否存在平衡索引。

算法

使用两个循环
外循环遍历所有元素，内循环检测外循环选择的当前索引是否为平衡索引
运行一个循环遍历数组
对于每个索引，找到当前索引左边和右边的元素和
如果左和右的元素和相等，那么当前索引是平衡索引
否则，返回-1
该解决方案的时间复杂度是O(n2)

示例

<!DOCTYPE html>
<html>
<body>
   <h3>Input Array: [-7, 1, 5, 2, -4, 3, 0]</h3>
   <script>

      // Input array
      const arr = [-7, 1, 5, 2, -4, 3, 0];

      // Flag to check if equilibrium index is found or not
      let equilibriumIndexFound = false;

      // Loop through each index i of the array
      for (let i = 0; i < arr.length; i++) {
         let leftSum = 0;
         let rightSum = 0;

         // Calculate the sum of elements to the left of i
         for (let j = 0; j < i; j++) {
            leftSum += arr[j];
         }

         // Calculate the sum of elements to the right of i
         for (let j = i + 1; j < arr.length; j++) {
            rightSum += arr[j];
         }

         // Check if the sum of elements to the left and right of i is equal
         if (leftSum === rightSum) {
            document.body.innerHTML += `The equilibrium index of the array is ${i}`;
            equilibriumIndexFound = true;
            break;
         }
      }

      // Check if equilibrium index is not found
      if (!equilibriumIndexFound) {
         document.body.innerHTML += `There is no equilibrium index in the array`;
      }
   </script>
</body>
</html>

请记住，上述代码仅为演示目的，不应用于生产环境，因为它没有进行优化。它的时间复杂度为O(n2)，对于大数组来说效率低下。

方法2：前缀和

计算数组的平衡索引的另一种方法是前缀和方法。使用这种方法，我们首先计算数组的前缀和，即从数组开头到当前索引的元素之和。然后，使用前缀和，我们遍历数组，检查当前索引左侧元素的总和是否等于当前位置右侧元素的总和。

算法

确定数组的前缀和。
遍历数组并使用前缀和来判断当前索引左侧元素的总和是否等于当前位置右侧元素的总和。
如果左侧元素的总和等于右侧元素的总和，则返回该索引作为平衡索引。
如果不存在平衡索引，则返回-1。

示例

<!DOCTYPE html>
<html>
<body>
   <h3>Equilibrium Index</h3>
   <script>
      function equilibriumIndex(arr) {
         let n = arr.length;

         // Calculate the prefix sum of the array
         let prefixSum = [];
         prefixSum[0] = arr[0];
         for (let i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1] + arr[i];
         }

         // Iterate through the array and check for equilibrium index
         for (let i = 0; i < n; i++) {
            let leftSum = (i == 0) ? 0 : prefixSum[i - 1];
            let rightSum = prefixSum[n - 1] - prefixSum[i];
            if (leftSum == rightSum) {
               return i;
            }
         }

         // No equilibrium index found
         return -1;
      }
      let arr = [-7, 1, 5, 2, -4, 3, 0];

      // Print the array
      document.write("Array: " + arr + "<br>");
      let result = equilibriumIndex(arr);
      if (result == -1) {
         document.write("No equilibrium index found");
      } else {
         document.write("Equilibrium index is " + result);
      }
   </script>
</body>
</html>

注意−使用前缀和方法找到数组的平衡指数的时间复杂度为O(n)，其中n是数组的大小

方法3：双指针

在这种方法中，我们可以跟踪两个指针，一个在数组的开始，一个在数组的末尾。通过这两个指针，我们可以计算出左侧和右侧的和，并将指针向彼此靠近，直到找到平衡指数。

算法

将leftSum和rightSum初始化为0，将n-1作为右指针。
从左到右遍历数组。
对于每个元素，将该元素添加到leftSum并从rightSum中减去。
如果leftSum等于rightSum，则将当前索引作为平衡指数返回。
如果找不到平衡指数，则返回-1。

示例

<!DOCTYPE html>
<html>
<body>
   <h3>Equilibrium index of an array - Two Pointers Approach</h3>
   <p id="input"></p>
   <p id="output"></p>
   <script>
      const arr = [-7, 1, 5, 2, -4, 3, 0];
      const n = arr.length;
      let leftSum = 0;
      let rightSum = 0;
      document.getElementById("input").innerHTML = "Input Array: " + arr.join(", ");
      for (let i = 0; i < n; i++) {
         rightSum += arr[i];
      }
      for (let i = 0; i < n; i++) {
         rightSum -= arr[i];
         if (leftSum === rightSum) {
            document.getElementById("output").innerHTML = "Equilibrium index: " + i;
            break;
         }
         leftSum += arr[i];
      }
      if (document.getElementById("output").innerHTML === "") {
         document.getElementById("output").innerHTML = "No equilibrium index found";
      }
   </script>
</body>
</html>

注意−使用前缀和方法找到数组的平衡点的时间复杂度为O(n)，其中n是数组的大小。