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

本文关键字：一个 c++ 数组 在此之前 项目 | 更新日期: 2023-09-27 18:18:07

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

给定数组中在该项之前(或包含该项)的所有项的和，我想找到该数组中某项的索引。

例如

假设我有以下数组:

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

输入值为6，然后我需要返回索引2(在上面的例子中，索引3为零)，当给定10时，我应该返回索引4。

最快的方法是什么?在c++和c#中?

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

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

如果你需要为不同的总和运行多个查询，创建一个数组并在其中设置总和，像这样:

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

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

http://en.wikipedia.org/wiki/Binary_search_tree

相关文章：