第八题 数组中和替定值的2个数或者多个数

第八题 数组中和为定值的2个数或者多个数
题目1：输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。

例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。

题目2：如果需要求解多个数呢

如数组1,2,3,4,5,6,7,8,9,10中和为10的有10,9+1,8+2，.....

//寻找和为定值的两个数或者多个数
//指定数组中和为定值的2个数
#include <iostream>
using namespace std;
int main()
{
	int a[]={1,2,4,7,11,13};
	int beg=0;
	int end=sizeof(a)/sizeof(int)-1;
	int sum=15;
	for(;beg<end;)
	{
		if (a[beg]+a[end]>sum)
		{
			end--;
		}
		else
		{
			if (a[beg]+a[end]==sum)
			{
				cout<<a[beg]<<"+"<<a[end]<<"="<<sum<<endl;
				beg++;
				end--;
			}
			else
			{
				beg++;
			}
		}
	}
	return 0;
}
//1,2,3.....n中和为定值的多个数
#include <iostream>
#include <vector>
using namespace std;
vector<int> vec;
void getnum(int sum,int *a,int leg)
{
	if (sum<=0||leg<0)
	{
		return;
	}
	if (*(a+leg)==sum)
	{
		for (auto it=vec.begin();it!=vec.end();++it)
		{
			cout<<*it<<"+";
		}
		cout<<*(a+leg)<<endl;
	}
	vec.push_back(*(a+leg));
	getnum(sum-*(a+leg),a,leg-1);
	vec.pop_back();
	getnum(sum,a,leg-1);
}
int main()
{
	//这边数组可以是任意的，后面调用的话就需要排序了
	int a[]={1,2,3,4,5,6,7,8,9,10};
	getnum(10,a,sizeof(a)/sizeof(int)-1);
	return 0;
}