学步园

一个整数数列，元素取值可能是1~N（N是一个较大的正整数）中的任意一个数，相同数值不会重复出现。
设计一个算法，找出数列中符合条件的数对的个数，满足数对中两数的和等于N+1。

复杂度最好是O(n)，如果是O(n2)则不得分

方法一：排序后，定义两个指针begin,end分别指向数组的第一个和最后一个元素。然后按以下规则移动指针：

1.  如果*begin + *end = N+1,那么找到一个解，同时begin++,end--

2.  如果*begin + *end > N+1,那么说明不等式后项应该减小，所以end--;

3.  如果*begin + *end < N+1,那么说明不等式前项应该增大，所以begin++;

4.  重复以下过程直到end<begin

代码如下：

int main()
{
	int a[] = {1,3,4,7,8,9,10};
	int sum = 11;
	int len = sizeof(a)/sizeof(int);
	sort(a,a+len);
	int high = len-1;
	int low = 0;
	while(low<high)
	{
		if(a[low]+a[high] == sum)
		{
			cout<<a[low]<<" + "<<a[high]<<" = "<<sum<<endl;
			low++;
			high--;
		}else if(a[low]+a[high]<sum)
		{
			low++;
		}else{
			high--;
		}
	}
	getchar();
	return 0;
}

方法二：构建一个辅助数组B，b[i] = N+1 – a[i].然后建立两个指针分别指向数组a的头部(begin)，和数组b的尾部(end)。按以下规则移动指针：

1.  如果a[begin] == b[end],那么找到一组解a[end]+b[end]=N+1，begin++,end--;

2.  如果a[begin] > b[end],那么end--;

3.  如果a[begin] < b[end],那么begin++;

4.  直到begin>end;

时间复杂度为O(N),空间复杂度O(N);

using namespace std;
int main()
{
	int a[] = {1,3,4,7,8,9,10};
	int sum = 11;
	int len = sizeof(a)/sizeof(int);
	int *b = (int *)malloc(sizeof(len));
	for(int i=0;i<len;i++)
		b[i]=sum-a[i];
	int high = len-1;
	int low = 0;
	while(low<high)
	{
		if(a[low]==b[high])
		{
			cout<<a[high]<<" + "<<b[high]<<" = "<<sum<<endl;
			low++;
			high--;
		}else if(a[low] > b[high])
		{
			high--;
		}else{
			low++;
		}
	}
	getchar();
	return 0;
}