c# - 如何在数组中找到一个项目，该项目之前所有值的总和是特定值？ (C++ 和 C#)

Question

假设我有一个具有特定大小(比如 1000)的整数数组

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

例如假设我有以下数组:

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

输入值为 6，那么我需要返回索引 2(上例中 3 的从零开始的索引)，当给定 10 时，我应该返回索引 4。

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

Answer 1

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

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

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)) 中的索引。