在范围内查找元素的高效查询
Efficient query for finding an element in a range
我遇到一个问题，我需要找到一个特定的成对总和，其中索引中的第一个元素的索引 > i。
示例：
[1, 2, 3, 4, 6]（索引 0 到 4）
target_sum = 9
现在，我需要从这个数组中找到一个成对求和，其中索引中的第一个元素的索引 > i。
现在，显而易见的解决方案是：
- 计算成对总和数组。
[1+2, 1+3, 1+4, 1+6, 2+3, 2+4, 2+6, 3+4, 3+6, 4+6] [ O(n^2) ]
- 遍历索引
i+1 到 n 以找到 target_sum。 [ O(n^2) ] (n为原数组的长度)
现在，主要问题是2。即使我无法改进（1），我也需要改进（2），因为这个会被很多人质疑。
我想到的一种方法：
- 从成对求和数组中创建索引、值对数组。 O(n^2) [n为原长度]
- 先按值排序数组，再按索引排序。 O(n^2 * logn)
- 对于每个查询，运行 二进制搜索以查找值存在的区间。 O(logn)
- 运行 对该区间的另一个二进制搜索以查找索引 >
i.
有什么优雅更好的方法吗？
在 O(n^2) 中创建地图 sum -> highest first element index。然后通过在映射中查找目标总和并确定 highest first element index 是否高于 i.
来回答 O(1) 中的每个查询
我遇到一个问题，我需要找到一个特定的成对总和，其中索引中的第一个元素的索引 > i。
示例：
[1, 2, 3, 4, 6]（索引 0 到 4）
target_sum = 9
现在，我需要从这个数组中找到一个成对求和，其中索引中的第一个元素的索引 > i。
现在，显而易见的解决方案是：
- 计算成对总和数组。
[1+2, 1+3, 1+4, 1+6, 2+3, 2+4, 2+6, 3+4, 3+6, 4+6][ O(n^2) ] - 遍历索引
i+1到n以找到 target_sum。 [ O(n^2) ] (n为原数组的长度)
现在，主要问题是2。即使我无法改进（1），我也需要改进（2），因为这个会被很多人质疑。
我想到的一种方法：
- 从成对求和数组中创建索引、值对数组。 O(n^2) [n为原长度]
- 先按值排序数组，再按索引排序。 O(n^2 * logn)
- 对于每个查询，运行 二进制搜索以查找值存在的区间。 O(logn)
- 运行 对该区间的另一个二进制搜索以查找索引 >
i.
有什么优雅更好的方法吗？
在 O(n^2) 中创建地图 sum -> highest first element index。然后通过在映射中查找目标总和并确定 highest first element index 是否高于 i.
O(1) 中的每个查询