用于查找范围中元素的高效查询

Question

我面临一个问题，我需要找到一个特定的成对和，其中索引中的第一个元素具有索引>CCD_ 1。

示例：

[1, 2, 3, 4, 6](索引0至4(

target_sum=9

现在，从这个数组中，我需要找到一个成对和，其中索引中的第一个元素的索引>i。

现在，显而易见的解决方案是：

1. 计算成对和数组。[1+2, 1+3, 1+4, 1+6, 2+3, 2+4, 2+6, 3+4, 3+6, 4+6][O(n^2(]
2. 循环索引i+1到n以查找target_sum。[O(n^2(](n为原始数组的长度(

现在，主要问题是2。即使我不能改进(1(，我也需要改进(2(，因为这会受到很多质疑。

我想到的一种方法是：

1. 从成对和数组中生成一个索引、值对数组。O(n^2([n为原始长度]
2. 先按值对数组进行排序，然后按索引进行排序。O(n^2*logn(
3. 对于每个查询，运行二进制搜索以查找值所在的间隔。O(logn(
4. 在该间隔上运行另一个二进制搜索以查找索引>i

有什么优雅更好的方法吗？

Answer 1

在i1中创建映射sum -> highest first element index。然后通过在映射中查找目标和并确定highest first element index是否高于i来回答O(1)中的每个查询。