给定一个排序的整数数组,我们如何找到一对和为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)
。
这可能更快。