algorithm - 在范围内查找元素的高效查询

Question

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

例子：

[1, 2, 3, 4, 6]（索引0到4）

目标总和 = 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（登录）
4. 在该间隔上运行另一个二进制搜索以找到索引 > i。

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

Answer 1

sum -> highest first element index在 中创建地图O(n^2)。O(1)然后通过在地图中查找目标总和并确定是否highest first element index高于 来回答每个查询i。