找出数组中和为N的一对数
/*
find the pair in an array .... that sum up to particular number
Company:Linkedin
Date:8/11/2011
*/
#include
#include
#include

int randomPartition(int A[], int low, int high);
void quickSort(int A[],int low, int high);
bool findPair(int A[],int size,int sum,std::pair& result);
void quickSort(int A[], int low, int high)
{
if(low>=high)
return;
int pivot=randomPartition(A,low,high);
quickSort(A,low,pivot-1);
quickSort(A,pivot+1,high);
}
int randomPartition(int A[], int low, int high)
{
srand(time((int)0));
int index=low+rand()%(high-low+1);
int t=A[high];
A[high]=A[index];
A[index]=t;
int key=A[high];
int i=low-1;
for(int j=low; j {
if(A[j]<=key)
{
i++;
int t=A[i];
A[i]=A[j];
A[j]=t;
}
}
i++;
t=A[high];
A[high]=A[i];
A[i]=t;
return i;
}
bool findPair(int A[],int size,int sum,std::pair& result)
{
quickSort(A,0,size-1);
int i=0;
int j=size-1;
while(i {
if(A[i]+A[j]==sum)
{
result.first=A[i];
result.second=A[j];
return true;
}
else if(A[i]+A[j] i++;
else
j--;
}
return false;
}
void main()
{
int A[10]={-2,-5,1,4,3,9,6,5,7,0};
int sum;
std::cout<<"Please enter a sum value\n";
std::cin>>sum;
std::pair result(0,0);
if(findPair(A,10,sum,result))
std::cout< else
std::cout<<"No pair found\n";
}
本文出自 “面试” 博客