aks*_*hay 4 algorithm array-algorithms
给定一个排序的整数数组,我们怎样才能找到一对总和为K的整数？
例如array = 1,3,5,6,0,K = 6答案是1和5.
应尽量减少时间复杂性.
你可能想看看这篇博文:
http://www.codingatwork.com/2011/07/array-sum/
我的方法是对列表进行二进制搜索K/2,然后a向左走一个变量,b向右走另一个变量,试图找到解决方案a+b=K.
我们的想法是a从小于或等于的最大数字K/2开始b,从最小的数字开始a.再次,使用二进制搜索来查找a并b成为数组中的下一个元素.然后
a+b = K,那么return (a,b).a+b < K,那么移动b到正确的一个位置.a+b > K,则a向左移动一个位置.当然,你可以跳过二进制搜索,只是从a数组的开头和数组b的末尾开始,然后再做
a+b = K,那么return (a,b).a+b < K,那么移动a到正确的一个位置.a+b > K,则b向左移动一个位置.这可能更快.