n个数找三个数，和等于c

先排序，复杂度o(nlgn)，再处理。可以做到O(n2)，不知道还有没有更好的方法。

#include <iostream>
#include <list>
using namespace std;

//O(n3)
void help1(int a[],int length,int value)
{
	for(int i=0;i<length-2;i++)
		for(int j=i+1;j<length-1;j++)
			for(int k=j+1;k<length;k++)
			{
				if(a[i]+a[j]+a[k]==value)
					cout<<a[i]<<" "<<a[j]<<" "<<a[k]<<endl;
			}
}

//recursive
list<int> ilist;
void find(int a[],int length,int start,int m,int sum)
{
	if(sum==0&&m==0)
	{
		list<int>::iterator iter=ilist.begin();
		for( ;iter!=ilist.end();iter++)
			cout<<*iter<<" ";
		cout<<endl;
		return;
	}
	if(start<length){
		ilist.push_back(a[start]);
		find(a,length,start+1,m-1,sum-a[start]);
		ilist.pop_back();
		find(a,length,start+1,m,sum);
	}
}

//O(n2)
void help2(int a[],int length,int value)
{
	int result;
	for(int i=0;i<length;i++)
	{
		result=value-a[i];
		for(int j=i+1,k=length-1;j<k;)
		{
			if(a[j]+a[k]>result)
				k--;
			else if(a[j]+a[k]<result)
				j++;
			else 
			{
				cout<<a[i]<<" "<<a[j]<<" "<<a[k]<<endl;
				j++;k--;
			}
		}
	}
}

int main()
{
	int a[]={1,2,3,4,5,6,7,8,9,10};
	find(a,10,0,3,15);
	//help1(a,10,15);
}

最后

以上就是忧伤小丸子为你收集整理的n个数找三个数，和等于c的全部内容，希望文章能够帮你解决n个数找三个数，和等于c所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。