经典指数          
原因
3792
浏览数
0
收藏数
 

给定一个整数sum,从有N个有序元素的数组中寻找元素a,b,使得a+b的结果最接近sum,最快的平均时间复杂度是:
  • O(n)
  • O(nlogn)
  • O(n^2)
  • O(logn)

     举报   纠错  
 
切换
1 个答案

答案:O(n)

思想类似于两端向中间扫描

1、设定两个指针P1、P2,分别指向数组开始和结尾,即P1指向最小值,P2指向最大值;

2、计算 *P1+*P2 的值为 SUM,与 sum 比较,记录它们的差值 DIF 和 SUM,若 SUMsum,P2--;

3、重复以上过程直到DIF最小

 
切换
撰写答案