1. 给一个有N个整数的数组S..和另一个整数X,判断S里有没有2个数的和为X，
请设计成O(n*log2(n)）的算法。
/*
1. 给一个有N个整数的数组S..和另一个整数X,判断S里有没有2个数的和为X，
请设计成O(n*log2(n)）的算法。
快排,头尾夹逼.
*/
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100
typedef pair<int,int> Pair;
Pair findSum(int *s,int n,int x)
{
sort(s,s+n); //排序
int *begin=s,*end=s+n-1;//首尾
while(begin<end) //俩头夹逼，很经典的方法
{
if(*begin+*end>x)
end--;
else if(*begin+*end<x)
begin++;
else
return Pair(*begin,*end);
}
return Pair(-1,-1);
}
int main()
{
int arr[N];
int n,x,i;
while(1)
{
cout<<"请输入数组元素的个数n(-1结束)："<<endl;
cin>>n;
if(n==-1) break;
cout<<"请输入"<<n<<"个元素："<<endl;
for(i=0;i<n;i++)
cin>>arr[i];
cout<<"请输入两个元素的和："<<endl;
cin>>x;
Pair ret=findSum(arr,n,x);
cout<<ret.first<<","<<ret.second<<endl;
}
return 0;
}
/*
8
3 -4 7 8 12 -5 0 9
11
5
1 4 5 -2 3
3
-1
*/
