有序数列中查找和为某定值的两个数

输入一个已经按升序排序过的数组和一个数字k，在数组中查找两个数，使得它们的和正好是k。要求时间复杂度是O(n)。

如果有多对数字的和等于输入的数字，输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。

两种思路

①设置两个指针，begain指向数组的第一个元素，end指向最后一个元素，判断两个数的和，若小于k，则begain后移，反之end迁移，直到找到符合要求的两个数或两指针相遇

②取最后数组中最后一个数（最大数）max，new一个大小为max的数组b[]，对于每个元素a[i]，令b[ a[i] ]=1，其余元素为0。（类似哈希表）

然后遍历a[]，若b[ sum – a[i] ]==1，则找到这样的一堆数。

满足时间复杂度为On的要求，但空间复杂度可能很大。。。。

思路一：

<pre name="code" class="cpp">#pragma once
#include<iostream>
using namespace std;

void match(int a[], int size,int sum)
{
	bool found = false;
	int begain = 0;
	int end = size - 1;
	while (begain < end&&!found)
	{
		if (a[begain] + a[end] == sum)
		{
			cout << a[begain] << " " << a[end] << endl;
			found = true;
		}
		else
			if (a[begain] + a[end] > sum)
				end--;
			else
				begain++;
	}
	if (!found)
		cout << "there is no such kind of match" << endl;
}

void main()
{
	int a[6] = { 1, 2, 4, 7, 12, 15 };
	int sum = 15;
	match(a, 6, sum);
	system("pause");
}