arrays - 算法 - 找到中心索引

Question

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

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

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

另一个整数将是所有整数的总和。

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

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

Answer 1

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