【微软谷歌面试100题--【14】有序序列的两数之和等于给定的数sum

第14题：

题目：输入一个已经按升序排序过的数组和一个数字sum，在数组中查找两个数，使得它们的和正好是输入的那个数字。

要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。

例如输入数组1、2、4、7、11、15 和数字15。由于4+11=15，因此输出4 和11。

看到这个题目的时候，我们的思路不由的想，怎么样才能更好更快的去实现？

我们可以这样思考，既然是有序，那么用两个指针i,j分别指向最小的和最大，让其先相加，会得到一个数M；

如果 M>sum，则 j--；

如果 M<sum，则 i++;

如果 M==sum，则打印出响应的值，并且 j--；i++，寻找下一对满足的值；

如果 i>j，此时就要跳出循环。

下面我们看代码：

package qyq.Algorithm.Algorithm14;/** * 实现一个有序的数组，使得两个数的和等于给定的数值M * @author qi * @creation 2012-8-10 */public class Algorithm14_0 {static void getSum(int []a,int sum){int length=a.length;int i,j;i=0;j=length-1;while(i<j){if(a[i]+a[j]>sum){j--;}else if(a[i]+a[j]<sum){i++;}else{System.err.println(a[i]+"  "+a[j]);i++;j--;}}}public static void main(String args[]){int a[]={1,3,4,7,8,9,9,12};int sum=13;getSum(a, sum);}}