c# - 如何在数组中找到之前所有值的总和是特定值的项目？（C++ 和 C#）

Question

假设我有一个特定大小的整数数组（比如 1000）

我想在这个数组中找到一个项目的索引，给定这个项目之前数组中所有项目的总和（或包括这个项目）。

例如假设我有以下数组：

 int[] values={1,2,3,1,3,6,4,8,2,11}

输入值为 6，然后我需要返回索引 2（上例中的 3 基于零的索引），当给定 10 时，我应该返回索引 4。

最快的方法是什么？在 C++ 和 C# 中？

score 2 · Accepted Answer

如果你只需要做一次，那么朴素的方式也是最快的方式：遍历数组，并保持运行总数。达到目标总和后，返回当前索引。

如果您需要针对不同的总和运行多个查询，请创建一个数组并在其中设置总和，如下所示：

var sums = new int[values.Length];
sums[0] = values[0];
for (int i = 1 ; i < sums.Length ; i++) {
    sums[i] = sums[i-1] + values[i];
}

如果所有值都是正数，您可以运行二进制搜索sums以获取O(log(n)).

score 0 · Accepted Answer

学习 BST，这将是解决您问题的最快算法：

2 回答 2