给定数组A，大小为n，现给定数X，判断A中是否存在两数之和等于X

题目：给定数组A，大小为n，现给定数X，判断A中是否存在两数之和等于X

思路一：

1，先采用归并排序对这个数组排序，

2，然后寻找相邻<k,i>的两数之和sum，找到恰好sum>x的位置，如果sum=x则返回true，

3，找到位置后，保持i不变，从k处向前遍历，直到找到A[k]+A[i]等于x，并返回TRUE，如果找不到，则返回false。

论证步骤3：当前找到的位置恰好A[k]+A[i]>x，且前一位置的sum<x；

　　　　　所以A[i]前面的数（不包括A[i]）无论取哪两个数都不可能使和等于x，只能小于x

　　　　　对位置k向前寻找时，当寻找到A[k]+A[i]=sum，返回true；当寻找到sum<x时，令k=i，跳出对k的循环，继续寻找

　　　　　当所有的路径寻找完之后，返回false，没找到

代码如下：

 1     public boolean ExitSumX(int A[],int x)
 2     {
 3         //归并排序
 4         MessSort(A);
 5          
 6         int k=0;
 7         for(int i=1;i<A.length;i++)
 8         {
 9             if(i!=k)
10             {
11                 if(A[k]+A[i]==x)
12                     return true;
13                 else if(A[k]+A[i]<x)
14                     k=i;
15                 else
16                 {
17                     while(k>0)
18                     {
19                         k--;
20                         if(A[k]+A[i]==x)
21                             return true;
22                         else if(A[k]+A[i]<x)
23                             { k=i;break; };
24                     }
25                 }
26             }
27         }
28         return false;    
29     }

算法分析：归并排序时间为：O(nlgn)，寻找算法时间复杂度为O(n²)，算法整体时间复杂度为：O(n²)，可见算法不算太好

思路二：

这种算法时间复杂度为O(nlgn)，思路来自算法导论