如何使用JavaScript查找将数组分割为两个等和子集的索引
寻找数组等分索引的JavaScript实现
问题描述
我们需要查找数组中特定元素的索引,该索引可将数组切分为两个和相等的子集,切分时排除当前索引位置的元素。
示例说明
- 给定数组
p=[5,3,9,8],元素9的索引为x=2,符合要求:- 第一个分区是
[5,3],和为8 - 第二个分区是
[8],和为8
- 第一个分区是
- 更多测试示例:
- 输入
p=[3,2,1,1,3,3],输出x=3 - 输入
p=[3,17,2,1],输出x=1
- 输入
实现思路
采用单次遍历的高效方案,时间复杂度为O(n):
- 先计算整个数组的总和
- 遍历数组时维护左侧元素的累加和
- 右侧元素的和可以通过「总和 - 左侧累加和 - 当前元素值」直接计算得到,不需要重复求和
- 当左侧累加和等于右侧和时,直接返回当前索引即可
- 遍历结束没有找到符合要求的索引时返回-1
代码实现
function findEqualSplitIndex(arr) { const totalSum = arr.reduce((acc, curr) => acc + curr, 0); let leftSum = 0; for (let i = 0; i < arr.length; i++) { const rightSum = totalSum - leftSum - arr[i]; if (leftSum === rightSum) { return i; } leftSum += arr[i]; } return -1; }
测试验证
你可以直接用示例验证代码效果:
console.log(findEqualSplitIndex([5,3,9,8])) // 输出 2 console.log(findEqualSplitIndex([3,2,1,1,3,3])) // 输出 3 console.log(findEqualSplitIndex([3,17,2,1])) // 输出 1 console.log(findEqualSplitIndex([1,2,3])) // 输出 -1(无符合要求的索引)
内容的提问来源于stack exchange,提问作者Mr. Ivančić
相关产品推荐
相关产品推荐

