求两数组元素和小于上限k的最大和对应索引对的最高效方法

有比暴力法更优的方案，最优时间复杂度可以做到O(n log n + m log m)，远优于暴力法的O(nm)，适合数组长度较大的场景。

核心思路 #

利用排序+双指针的组合方法，步骤如下：

1. 预处理两个数组，将每个元素和它的原始索引绑定，避免排序后丢失原始位置信息，处理后格式为(元素值, 原始索引)。
2. 将预处理后的A、B数组都按元素值升序排序。
3. 初始化双指针：i 指向A数组的最左端（最小值位置，初始为0），j 指向B数组的最右端（最大值位置，初始为len(B)-1）。
4. 维护三个状态变量：当前找到的最大合法和max_sum（初始设为负无穷），对应原始索引res_i、res_j（初始设为-1）。
5. 遍历直到指针越界：
   • 计算当前和 s = A[i][0] + B[j][0]
   • 若s < k：当前和符合要求，若s大于max_sum则更新max_sum和对应的原始索引；之后将i右移，尝试用更大的A元素获得更大的合法和。
   • 若s >= k：当前和超出上限，将j左移，尝试用更小的B元素缩小总和。
6. 遍历结束后返回(res_i, res_j)即可。

示例验证 #

用题目给出的示例测试：

• 原A = [9,2,5]，预处理排序后为[(2, 1), (5, 2), (9, 0)]
• 原B = [2,1,6]，预处理排序后为[(1, 1), (2, 0), (6, 2)]
• k=5
  遍历过程：
• i=0, j=2：s=2+6=8 ≥5 → j左移为1
• i=0, j=1：s=2+2=4 <5 → 更新max_sum为4，对应索引(1,0)，i右移为1
• i=1, j=1：s=5+2=7 ≥5 → j左移为0
• i=1, j=0：s=5+1=6 ≥5 → j左移为-1，遍历结束
  最终输出(1,0)，和示例结果一致。

边界说明 #

如果所有元素对的和都≥k，最终返回的是(-1,-1)，可根据实际需求调整异常处理逻辑。

内容的提问来源于stack exchange，提问作者atprra