c++ - 查找输入数字以了解它在数组中的位置

Question

我有一个小算法问题。例如，我有一个数组。

array[10] = {23,54,10,63,52,36,41,7,20,22};

现在给定一个输入数字，例如 189，我想知道它应该位于哪个插槽中。 例如这个输入应该位于数组的第 4 个索引中，因为

23+54+10+63 = 150 and if we add 52 then sum will be 202 which will cover the range where 189 should lie. so the answer should be 4. 

我想找到一个摊销常数时间算法可能在第一步中我们对数组进行一些预处理，以便我们可以在常数时间内获得所有下一个查询。

输入的数字将始终介于 1 和数组中所有条目的总和之间
谢谢

Answer 1

如果您确实需要常数时间，请创建第二个数组，其大小是包含原始数组索引的最大总和值。所以 new_array[189] = 4;