给定一个排序的整数数组,我们如何找到一对和为k的整数?
例如,array = 1,3,5,6,0K = 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)
这可能更快。

09-30 14:01
查看更多