四数之和

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

有n个不同的整数，判断能否从中选4次，4个数和刚好为m。数字可重复选取。

Input:

输入包含多组测试，每组测试第一行是两个数n(1<=n<=)和m(0<=m<=10^9)。

第二行是n个数a1,a2,a3...an(0<=ai<=10^8);

Output:

对于每组测试，如果能从中找出4个数和为m，则输出YES，否则输出NO。

Sample Input:

Sample Output:

YES

YES

NO
解题思路：因为四数和中选取的每个数字可以重复，因此我们可以先将每每两个数的和存放到set容器中（注意元素具有唯一性即不重复性），然后使用find()来查找set中是否有m-*it这个元素即可，思路清晰，代码可以过，不超时！忽略系数，此解法时间复杂度是O（n^2）。
AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 int a[],n,m;

 set<int> t;

 bool findt(int obj){  //find()返回迭代器在容器中的位置

     return t.find(obj)==t.end();

 }

 int main()

 {

     while(cin>>n>>m){

         t.clear();

         for(int i=;i<n;++i)

             cin>>a[i];

         for(int i=;i<n;++i)

             for(int j=;j<n;++j)

                 t.insert(a[i]+a[j]);  //每每两个数相加

         bool flag=false;  //标记set中是否有这个元素

         for(set<int>::iterator it=t.begin();it!=t.end();++it)

             if(!findt(m-*it)){flag=true;break;}

         if(flag)cout<<"YES"<<endl;

         else cout<<"NO"<<endl;

     }

     return ;

 }

巴特西

ACM_四数之和

四数之和

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

Input:

Output:

Sample Input:

Sample Output:

最新文章

热门文章