学步园

给定一个整型数组a[]和一个数sum，设计一个算法找到数组中所有的整数对(a[i], a[j])，其中a[i] + a[j] == sum。

思路：

可以用bitmap或者哈希来做，这样可以达到O(n)的复杂度。遍历一次数组，将bitmap[a[i]]的值置为1，然后再去检查bitmap[sum - a[i]]的值是否为1，这样就找到满足条件的整数对。如果数组中有重复数字且整数对中的数字不能重复计算，例如：(2, 2, 3)，sum = 5，正确结果为{(2, 3)}，但bitmap的结果为{(2, 3), (2, 3)}，此时可以用哈希表，hash[a[i]]的值为a[i]的出现次数。但是这样的方法可能会造成大量的空间浪费，比如数组的大小较小，但数组中最大值非常大。

另外一个思路就是先排序，然后设置头尾指针往中间扫描，复杂度为O(nlogn)。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void FindPair(vector<int> ivec, int sum)
{
	if (ivec.size() < 2)
		return;
	sort(ivec.begin(), ivec.end());
	int left = 0, right = ivec.size() - 1;
	while (left < right)
	{
		if (ivec[left] + ivec[right] == sum)
		{
			cout << ivec[left] << " " << ivec[right] << endl;
			++left;
			--right;
		}
		else if (ivec[left] + ivec[right] > sum)
			--right;
		else
			++left;
	}
}

int main()
{
	vector<int> ivec;
	for (int i = 1; i <= 6; ++i)
		ivec.push_back(i);
	int sum = 5;
	FindPair(ivec, sum);
	return 0;
}