求数组平衡点的算法

Question

• 任务:找到数组的平衡点；返回索引，如果将数组分解为left，那么此时的right将在两边创建相同的和。例如:给定数组，[2, 4, 5, 1, -2, 7, 2, 1, 4]返回的值应该是：3左：2, 4, 5, 1 = 12右：-2, 7, 2, 1, 4 = 12

public static arrayBalance(input?: number[]): any {
    let sum = 0;
    for(let i=0; i

时间复杂度：O(2n)，空间复杂度：O(1)

我说得对吗？您有不同的实施建议吗？

Answer 1

首先，在接口上有一个建议:使用null来表示不匹配，而不是-1，因为这使得强制调用者检查无解决方案(即，如果他们试图使用未检查的函数返回作为索引，-1只会在运行时失败，而null将在transpile时失败)。

function arrayBalance(input: number[]): number | null {

在阅读代码时，我对变量名感到困惑-- mid实际上不是一个中点，它是每一半的预期和。在用let而不是const声明的所有变量与信息不足的名称(为什么有sum和sum2?)之间，很难一眼就知道哪些值正在重新计算，哪些是常量。

与其用六行代码来找到我们希望“拆分”的每一方都有的“半和”，不如用一种方式(简洁是智慧的灵魂，而这类事情正是reduce函数的目的)，并声明它为const，因为一旦我们计算出函数的其余部分，它不会改变：

const halfSum = input.reduce((a, b) => a + b) / 2;

从这里开始，我们所需要做的就是找出我们需要的数组元素总数达到相等的halfSum。

下面是我编写其余部分的方法，将数组“左侧”的运行总数表示为leftSum，并对数组索引执行一个简单的for循环：

let leftSum = 0;
for (let i = 0; i < input.length; i++)
{
    leftSum += input[i];
    if (leftSum == halfSum)
        return i;
}
return null;

当我们在i中迭代时，我们在i (leftSum)的左边构建一个所有事物的和。我们的目标是使leftSum与halfSum相等。如果在循环中找不到解决方案，则返回null。

用不等式比较来优化无解情况是很有诱惑力的，但是考虑到输入数组中有大量随机分布的负数的情况！halfSum可以是负的，也可以是零的，而leftSum可以是上升后下降，然后再上升然后再下降，随着i的增加，所以除非你已经遍历了整个数组，否则你永远无法确定一个解决方案是不存在的。

还要注意，有可能有多个有效的解决方案；这个实现总是返回实例中最低的一个，但是您可以编写这个函数的一个版本，它总是遍历整个数组，并返回它找到的所有解决方案的另一个数组。