July面试整理系列--（4）

题目描述：

给一个有N个整数的数组S..和另一个整数X，判断S里有没有2个数的和为X，
请设计成O（n*log2(n)）的算法。

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <cstring>
 6 #include <vector>
 7 #include <string>
 8 #include <climits>
 9 using namespace std;
10 
11 /*
12 先排序，O(n*log2n)；
13 从头尾开始逼近；
14 如果当前两个数的和小于target，那么左下标递增；
15 如果当前两个数的和大于target，那么右下标递减；
16 */
17 typedef pair<int,int> Pair;
18 Pair fun(vector<int> arr,int target)
19 {
20     if(arr.size() == 0)
21     {
22         return Pair(-1,-1);
23     }
24 
25     sort(arr.begin(),arr.end());
26     int s = 0;
27     int e = arr.size()-1;
28     while(s < e)//两个不同位置的数
29     {
30         if(arr[s]+arr[e] < target)
31             ++s;
32         else if(arr[s]+arr[e] > target)
33             --e;
34         else
35         {
36             return Pair(arr[s],arr[e]);
37         }
38     }
39 }
40 
41 int main()
42 {
43     int a[8]=
44     {
45         3, -4, 7, 8, 12, -5, 0, 9
46     };
47     int target = 12;
48     vector<int> vec;
49     for(int i = 0 ; i < 8 ; ++i)
50     {
51         vec.push_back(a[i]);
52     }
53     Pair res;
54     res = fun(vec,target);
55     cout<<res.first<<" "<<res.second<<endl;
56     return 0;
57 }