数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究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)，稍后将解释。使用两个循环很简单。目标是找到每个索引范围的元素之和，并查看是否存在平衡索引。外循环遍历数组，内循环检查是否存在平衡索引。
算法
使用两个循环
外循环遍历所有元素，内循环检查外循环选择的当前索引是否是平衡索引。
遍历数组
对于每个索引，找到当前索引左侧和右侧元素的和
如果left_sum和right_sum相等，则当前索引是平衡索引
否则，返回-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初始化为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是数组的大小。
结论
在本博文中，我们讨论了通过各种方法查找数组的平衡索引。其中一些方法包括使用循环、前缀和和双指针方法。希望您觉得这些信息有用。
423 次浏览
