给定一个整数sum,从有N个有序元素的数组中寻找元素a,b,使得a+b的结果最接近sum,最快的平均时间复杂度是: O(n) O(nlogn) O(n^2) O(logn)
答案:O(n)
思想类似于两端向中间扫描
1、设定两个指针P1、P2,分别指向数组开始和结尾,即P1指向最小值,P2指向最大值;
2、计算 *P1+*P2 的值为 SUM,与 sum 比较,记录它们的差值 DIF 和 SUM,若 SUMsum,P2--;
3、重复以上过程直到DIF最小