本文介绍了在两个排序数组最近对总和的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
整数给定两个有序阵列， 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[]?"
这篇关于在两个排序数组最近对总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！