编程之美-快速寻找满足条件的2个数（扩展问题）
时间：2010-09-23 来源：wsnhyjj
原题是：
能否快速找出一个数组中的两个数字，让这两个数字之和等于一个给定的值？
这个可以将数组排序，然后前后各一个指针向中间靠拢寻找。
扩展问题1：
如果将问题中的“两个数字”改成“三个数字”或“任意个数字时”，你的解答时什么？
写了一段代码，查找一个集合中是否存在一个子集，其中数字之和等于给定的值(given),有则返回子集，没有就返回空。
/*
* Description:
* 查找一个集合中是否存在一个子集，其中数字之和等于给定的值。
* Author :FinL
* Language: C++
* Date : 2010-09-23
*/
#include <iostream>
using namespace std; int FindSubset(int* arr,int sum,int*include,int n)
{
int curr=0;
int tmp_sum=0;
while(curr>=0)
{
if(0==include[curr])
{
include[curr]=1;
tmp_sum += arr[curr];
if(tmp_sum==sum)
return 1;
else if(tmp_sum>sum)
{
include[curr]=0;
tmp_sum -= arr[curr];
}
curr++;
}
if(curr>n-1)
{
while(1==include[curr-1])
{
curr--;
include[curr]=0;
tmp_sum -= arr[curr];
if(curr<1)
return 0;
}
while(0==include[curr-1])
{
curr--;
if(curr<1)
return 0;
}
include[curr-1]=0;
tmp_sum -= arr[curr-1];
}
}
return 0;
} int main()
{
int arr[]={1,2,4,6,3,7,97,46,32,25,12,11};
int n;
int target=112; n=sizeof(arr)/sizeof(arr[0]); int *include = new int[n];
memset(include,0,n*sizeof(int)); if(FindSubset(arr,target,include,n))
{
for(int i=0;i<n;i++)
{
if(include[i])
cout<<arr[i]<<" ";
}
}
else
{
cout<<"Find no subset"<<endl;
}
cout<<endl;
return 0;
}
using namespace std; int FindSubset(int* arr,int sum,int*include,int n)
{
int curr=0;
int tmp_sum=0;
while(curr>=0)
{
if(0==include[curr])
{
include[curr]=1;
tmp_sum += arr[curr];
if(tmp_sum==sum)
return 1;
else if(tmp_sum>sum)
{
include[curr]=0;
tmp_sum -= arr[curr];
}
curr++;
}
if(curr>n-1)
{
while(1==include[curr-1])
{
curr--;
include[curr]=0;
tmp_sum -= arr[curr];
if(curr<1)
return 0;
}
while(0==include[curr-1])
{
curr--;
if(curr<1)
return 0;
}
include[curr-1]=0;
tmp_sum -= arr[curr-1];
}
}
return 0;
} int main()
{
int arr[]={1,2,4,6,3,7,97,46,32,25,12,11};
int n;
int target=112; n=sizeof(arr)/sizeof(arr[0]); int *include = new int[n];
memset(include,0,n*sizeof(int)); if(FindSubset(arr,target,include,n))
{
for(int i=0;i<n;i++)
{
if(include[i])
cout<<arr[i]<<" ";
}
}
else
{
cout<<"Find no subset"<<endl;
}
cout<<endl;
return 0;
}
相关阅读 更多 +
