高效查询首元素下标大于i的成对和的优化方案咨询
成对和查询优化方案
更优实现方案:哈希表预分组
该方案预计算开销比你当前的方案更低,查询逻辑更简单,效率基本持平甚至更高:
预计算阶段(时间复杂度O(n²))
直接构造哈希映射:
- 哈希表的
key为成对和值 - 哈希表的
value为天然升序的首元素下标列表
预计算流程: - 按从小到大的顺序遍历所有首元素下标
a(范围:0 ≤ a ≤ n-2,n为原数组长度) - 对每个
a,遍历尾元素下标b(范围:a+1 ≤ b ≤ n-1) - 计算和值
sum = arr[a] + arr[b],直接将a追加到哈希表中sum对应的列表末尾
因为遍历首元素下标
a是从小到大执行的,所以每个和值对应的下标列表天然就是升序的,不需要额外排序,直接省掉了你原方案中O(n²logn)的全局排序开销。
查询阶段(平均时间复杂度O(logk),k为当前目标和对应的下标数量)
- 先查哈希表中是否存在目标和
target_sum,不存在直接返回空结果,这一步复杂度为O(1) - 如果存在对应值,对其绑定的升序下标列表做二分查找,找到第一个大于给定值
i的元素位置,该位置往后的所有下标都满足要求,直接返回对应结果即可
示例验证
以你给出的数组[1, 2, 3, 4, 6]为例,目标和9对应的首元素下标列表为[2]:
- 若查询时给定
i=1,二分查找后即可快速确认存在符合要求的成对和3+6=9 - 若查询时给定
i=2,则没有符合要求的结果
原方案的问题对比
你当前的优化方案需要对全部n²个二元组做全局排序,预计算阶段多出了O(n²logn)的排序开销,且查询时需要两次二分定位区间,实现复杂度更高,也更容易出现边界错误。
可选进阶优化(适合离线查询场景)
如果你可以提前收集到所有的查询请求,可以采用离线排序+双指针的方案,将总查询复杂度进一步降到O(Q + n²),其中Q为查询总次数,适合超大规模高频查询场景。
内容的提问来源于stack exchange,提问作者Zabir Al Nazi Nabil
相关产品推荐
相关产品推荐

