如何找出符合满足条件的数组对数的个数

在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;
}