寻找满足条件的两个数

题目：输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。如果有多对数字的和等于输入的数字，输出任意一对即可。

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

分析：1.直接穷举。从数组中任意选取两个数，判定它们的和是否为输入的那个数字。此方法与数组有序或者无序无关，时间复杂度为O(n)。

 1 #include <iostream.h>
 2 
 3 bool Find2Num(int *data,int n,int sum,int &num1,int &num2)
 4 {
 5     if (NULL==data || n<=1)
 6     {
 7         return false;
 8     }
 9 
10     for (int i=0;i<n;i++)
11     {
12         for (int j=i+1;j<n;j++)
13         {
14             if (data[i]+data[j]==sum)
15             {
16                 num1=data[i];
17                 num2=data[j];
18                 return true;
19             }
20             else
21             {
22                 continue;
23             }
24         }
25     }
26 
27     return false;
28 }
29 
30 void main()
31 {
32     int data[6]={1,2,4,7,15,11};
33     int sum=15;
34     int num1,num2;
35 
36     if (Find2Num(data,6,sum,num1,num2))
37     {
38         cout<<num1<<" "<<num2<<endl;
39     }
40     else
41     {
42         cout<<"doesn't exsit!"<<endl;
43     }
44         
45 }

2.对每个a[i],然后查找sum-a[i]是否也在原始序列中，在查找的过程中采用二分查找，然而二分查找需序列是有序的，所以需要对数组进行排序。排序所需的时间为O(N*logN)。对N个a[i]，每个都需要花费O(logN)的时间去查找，故查找的过程所需时间为O(N*logN).总的花费时间为O(N*logN+N*logN)=O(N*logN)。

 1 #include <iostream.h>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int BinarySearch(int *data,int n,int num)
 6 {
 7     int low=0;
 8     int high=n-1;
 9     int middle,position;
10     while(low<=high)
11     {
12         middle=(low+high)/2;
13         if (data[middle]<num)
14         {
15             low=middle+1;
16         }
17         else if (data[middle]>num)
18         {
19             high=middle-1;
20         }
21         else
22         {
23             position=middle;
24             
25             return position;
26         }
27     }
28 
29     
30     return -1;
31 }
32 
33 bool FindSum2(int *data,int n,int sum,int &num1,int &num2)
34 {
35     if (NULL==data || n<=1)
36     {
37         return false;
38     }
39 
40     int findnum,index;
41 
42     for (int i=0;i<n;i++)
43     {
44         findnum=sum-data[i];
45         index=BinarySearch(data,n,findnum);
46         if (index!=-1 && index!=i)
47         {
48             num1=data[i];
49             num2=data[index];
50             return true;
51         }
52         else
53         {
54             continue;
55         }
56     }
57 
58     return false;
59         
60 }
61 
62 void main()
63 {
64     int data[6]={1,2,4,7,15,11};
65     int sum=15;
66     int num1,num2;
67     sort(data,data+6);
68 
69     if (FindSum2(data,6,sum,num1,num2))
70     {
71         cout<<num1<<" "<<num2<<endl;
72     }
73     else
74     {
75         cout<<"doesn't exsit!"<<endl;
76     }
77         
78 }

3.如果数组是无序的，则首先采用快速排序算法排好序，所需时间为O(N*logN)。然后用两个指针i,j，分别指向数组的首端和尾端，令i=0,j=n-1；然后i++,j--;逐次判断a[i]+a[j]？=sum。如果某时刻a[i]+a[j]>sum，则j--，i不动;如果某时刻a[i]+a[j]<sum,则i++，j不动。终止条件是i>=j。此遍历过程的时间复杂度为O(N),所以此方法总的时间复杂度为O(N*logN+N)=O(N*logN).倘若数组本身是有序的，则此方法的时间复杂度降为O(N)。

 1 #include <iostream.h>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 bool Find2Num(int *data,int n,int sum,int &num1,int &num2)
 6 {
 7     if (NULL==data || n<=1)
 8     {
 9         return false;
10     }
11 
12     int *begin=data;
13     int *last=data+n;
14     sort(begin,last);//排序
15 
16     int low=0,high=n-1;
17     while(low<high)
18     {
19         if (data[low]+data[high]<sum)
20         {
21             low++;
22         }
23         else if (data[low]+data[high]>sum)
24         {
25             high--;
26         }
27         else
28         {
29             num1=data[low];
30             num2=data[high];
31             return true;
32         }
33     }
34 
35     return false;
36     
37 }
38 
39 void main()
40 {
41     int data[6]={1,2,4,7,15,11};
42     int num1,num2;
43     int sum=15;
44     bool flag=Find2Num(data,6,sum,num1,num2);
45     if (flag)
46     {
47         cout<<"exist two numers:"<<num1<<" and "<<num2<<" which theirs sum equal to "<<sum<<endl;
48     }
49     else
50     {
51         cout<<"doesn't exist!"<<endl;
52     }
53 }

 1 #include <iostream.h>
 2 #include <algorithm>
 3 #include <utility>
 4 using namespace std;
 5 
 6 
 7 pair<int,int> FindSum(int *data,int n,int sum)
 8 {
 9     if (NULL==data || n<=1)
10     {
11         return make_pair(-1,-1);
12     }
13     
14     sort(data,data+n);//排序
15 
16     int *begin=data;
17     int *last=data+n-1;
18 
19     while(begin<last)
20     {
21         if (*begin+*last<sum)
22         {
23             begin++;
24         }
25         else if (*begin+*last>sum)
26         {
27             last--;
28         }
29         else
30         {
31             return make_pair(*begin,*last);
32         }
33     }
34 
35     return make_pair(-2,-2);
36 }
37 
38 void main()
39 {
40     int data[6]={1,2,4,7,15,11};
41     int sum=15;
42     pair<int,int> p;
43     p=FindSum(data,6,sum);
44     cout<<p.first<<" "<<p.second<<endl;
45 }