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

Efficient query for finding an element in a range

我遇到一个问题,我需要找到一个特定的成对总和,其中索引中的第一个元素的索引 > i

示例:

[1, 2, 3, 4, 6](索引 04

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+1n 以找到 target_sum。 [ O(n^2) ] (n为原数组的长度)

现在,主要问题是2。即使我无法改进(1),我也需要改进(2),因为这个会被很多人质疑。

我想到的一种方法:

  1. 从成对求和数组中创建索引、值对数组。 O(n^2) [n为原长度]
  2. 先按值排序数组,再按索引排序。 O(n^2 * logn)
  3. 对于每个查询,运行 二进制搜索以查找值存在的区间。 O(logn)
  4. 运行 对该区间的另一个二进制搜索以查找索引 > i.

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

O(n^2) 中创建地图 sum -> highest first element index。然后通过在映射中查找目标总和并确定 highest first element index 是否高于 i.

来回答 O(1) 中的每个查询