在1~n个数中,找到某两个数的和等于另一数
第一种方法:两重for循环暴力,时间复杂度O(n*n)
第二种:使用二分,分别从首尾出发。时间复杂度O(n*logn)。当非排序时,需要先排序。
/* *********************************************** Author :bo-jwolf Created Time :2015年02月21日 星期六 22:24:59 File Name :311.cpp ************************************************ */ #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; const int MAX = 1005; int num[ MAX ], n, m; void Find( int *num, int Value ){ int l = 1, r = n; if( num == NULL ?? l < 1 && r > n ) return; while( l < r ){ int mid = ( l + r ) >> 1; if( num[ l ] + num[ r ] == Value ){ cout << num[ l ] << " " << num[ r ] << endl; l++; r--; } else if( num[ l ] + num[ r ] > Value ){ r--; } else{ l++; } } } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); while( cin >> n ){ for( int i = 1; i <= n; ++i ){ cin >> num[ i ]; } cin >> m; Find( num, m ); } return 0; }
第三种方法:Hash表,将数据存储在Hash表中,然后查找是否存在num[ value – num[ i ] ]。时间复杂度O(n+m)
/* *********************************************** Author :bo-jwolf Created Time :2015年02月21日 星期六 22:33:22 File Name :311a.cpp ************************************************ */ #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; const int MAX = 1005; int num[ MAX ]; int n, m; map<int,int> Hash; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); while( cin >> n ){ for( int i = 1; i <= n; ++i ) cin >> num[ i ]; for( int i = 1; i <= n; ++i ) Hash.insert( pair< int, int > ( num[ i ], num[ i ] ) ); cin >> m; for( int i = 1; i <= n; ++i ){ if( Hash.find( m - num[ i ] ) != Hash.end() ){ cout << num[ i ] << " " << m - num[ i ] << endl; } } } return 0; }