You need to enable JavaScript to run this app. 高效查询首元素下标大于i的成对和的优化方案咨询
优惠活动
大模型
产品
解决方案
定价
更多

高效查询首元素下标大于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为当前目标和对应的下标数量)

  1. 先查哈希表中是否存在目标和target_sum,不存在直接返回空结果,这一步复杂度为O(1)
  2. 如果存在对应值,对其绑定的升序下标列表做二分查找,找到第一个大于给定值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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.19 09:06:03