编程之美2.12快速寻找满足条件的2个数

题目：

对于一个数组，快速找出两个数字，让这两个数字的和等于一个给定的值，默认假设数组中肯定有至少一组符合要求。

数组a[]={5,6,1,4,7,8,9},sum=10.

解法一：

穷举，遍历数组中所有的2个数字，相加之和看是否等于给定的数字，时间复杂度为N（N-1）/2，既O(N^2)，这种方法效率不高。

 1 #include "iostream"
 2 using namespace std;
 3 
 4 void sum(int *a,int N){
 5     for(int i=0;i<N;i++){
 6         for(int j=i+1;j<N;j++)
 7         if(a[i]+a[j]==10)
 8             cout<<"a="<<a[i]<<" b="<<a[j]<<endl;
 9     }
10 }
11 int main(){
12     int data[] = {5, 6, 1, 4, 7, 9, 8};
13     int length=sizeof(data)/sizeof(data[0]);
14     sum(data,length);
15 }

解法二：
求2个数字之和，假定和为sum，对于元素a[i]只需判断数组中是否存在sum-a[i]，无序数组中查找一个数的时间复杂度为O(n),不对数组进行操作的时间复杂度仍为O（n^2）。如果对数组进行排序，然后才去二分查找的方法，查找一个元素的时间复杂度为O(log2n),总时间复杂度为O(n*log2n)。而排序的过程只需要进行一次，时间复杂度为O(N*log2n),所以总时间复杂度仍为O(n*log2n)。

解法三：

换个角度，对于有序序列，从两头分别取数，之和大于sum，j--，之和大于sumi++。将排序号的数组遍历一遍即可输出全部的结果。

 1 #include "iostream"
 2 #include "algorithm"
 3 using namespace std;
 4 
 5 void sum(int *a,int N){
 6 int i,j;
 7     for(i = 0,j = N-1;i<j;){
 8         if(a[i]+a[j]==10){
 9             cout<<a[i]<<","<<a[j]<<endl;
10             i++;
11         }
12         else if(a[i]+a[j]<10)
13             i++;
14         else 
15             j--;
16     }
17 }
18 int main(){
19     int data[] = {5, 6, 1, 4, 7, 9, 8};
20     sort(data, data+7);   //快速排序 
21     int length=sizeof(data)/sizeof(data[0]);
22     sum(data,length);
23 }

扩展问题：

1，将两个数字改为3个数字。

假设找到了3个数ai，aj，ak，ai+aj+ak=sum，既ai+aj=sum-ak。i,k从左侧遍历，j从右侧遍历。以sum=17为例，会输出三组满足条件的数。

 1 #include "iostream"
 2 #include "algorithm"
 3 using namespace std;
 4 
 5 void sum(int *a,int N){
 6 int i,j,k;
 7 for(k=0;k<N;k++)
 8     for(i = k+1,j = N-k-1;i<j;){
 9         if(a[i]+a[j]+a[k]==17){
10             cout<<a[i]<<","<<a[j]<<","<<a[k]<<endl;
11             i++;
12         }
13         else if(a[i]+a[j]+a[k]<17)
14             i++;
15         else 
16             j--;
17     }
18 }
19 int main(){
20     int data[] = {5, 6, 1, 4, 7, 9, 8};
21     sort(data, data+7);   //快速排序 
22     int length=sizeof(data)/sizeof(data[0]);
23     sum(data,length);
24 }

编程之美2.12快速寻找满足条件的2个数

相关推荐