• 大众点评2016研发工程师笔试真题

    2015/09/30 王先生 19 评论

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

a. O(n)
b. O(nlogn)
c. O(n^2)
d. O(logn)

选a     O(n)时间,2个指针从数组的开始位置和结束位置移动,和大于sum,left++,和小于sum,right–。更新最小的差值,和2个指针的值,移动时更新。差值为0,则结束

4 4 收藏


直接登录
最新评论