在两个排序数组最近对总和

本文介绍了在两个排序数组最近对总和的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

整数给定两个有序阵列， A 和 B ，和一个整数Ç ，我必须要找到 I，J 这样：

Given two sorted arrays of integers, a and b, and an integer c, I have to find i,j such that:

a[i] + b[j] <= c

和 A [I] + B [J] 是越大越好。

我能想到的最好的办法是在 0 （ N 登录 N ）的时间，即从第一个数组中的每个整数，寻找下界 CA [I] 的 任何人都可以给我建议一个更好的方式来做到这一点（也许在O（ N ）的时间）？

The best solution I can think of is in O(nlogn) time, taking every integer from first array and finding the lower bound of "c-a[i]". Can anyone suggest me a better way to do this (maybe in O(n) time)?

推荐答案

思考了一下这个问题，那么你可以问自己： 是否有必要，每次排序的B-阵列连续值从[]中进行搜索？

Thinking a bit about it, then you could ask yourself: "Is it necessary, each time, to search in the sorted b-array for successive values from a[]?"