arrays - 算法 - 找到中心索引

Question

给定一个大小为 int 的数组t，需要找到中心索引。中心索引x是整数（0 到 x-1）之和等于和（x+1 到 t-1）的索引。

我能想到的最好的算法是 O(n)。

我将有一个临时数组，其中包含之前所有整数的总和（不包括索引 x 处的整数）：因此在索引 1 处它将是 1，在 2 处它将是 2 和 1 的总和，依此类推。

另一个 int 将是所有 int 的总和。

我会在数组中循环两次，第一次是临时数组，另一个是查找两个部分是否相等。

有没有更好的算法 O(logn)？

Answer 1

由于您必须计算数组的一半的总和，因此无法在小于O(n). 因为您必须至少检查每个元素一次（以计算总和）。只有当我们可以根据某些条件跳过检查数组中的某些元素时，任何算法都可以logn，这在此处是不可能的。