performance - 对给定的一系列数字求和，以便尽可能多地重置求和算法

Question

我正在寻找一种有效的算法(不一定是代码)来解决以下问题:

给定 n 个总和为零的正数和负数，我们想找到一个起始索引，该索引将使累积和尽可能多地为零。

它不必采用特定的方式，但这里的重要性在于效率——我们希望算法/想法能够在小于二次“时间复杂度”的情况下实现这一点

一个例子:给定数字:2、-1、3、1、-3、-2:

如果我们用 2(第一个索引)进行 strat 求和，则总和只会一次为零(在求和结束时)，但是使用 -1 进行求和将在求和期间产生两次零。给定的数字可能有多个“最佳索引”，但我们希望至少找到这些索引中的一个。

我已经尝试使用二进制搜索来完成它，但没有取得太大进展 - 所以任何提示/帮助将不胜感激。

Answer 1

您可以计算前缀和。就前缀和而言，零是与起始位置具有相同前缀和值的位置。所以问题被简化为找到前缀和数组中出现频率最高的元素。它可以使用排序或哈希表有效地解决。

举个例子:
输入:{2, -1, 3, 1, -3, 2}
前缀和:{0, 2, 1, 4, 5, 2, 0}
出现频率最高的元素是 2。第一次出现的 2 位于第一个位置。因此，从第二个元素开始产生最佳答案。