给出一个长度为N的无序数组,数组中的元素为整数,有正有负包括0,并互不相等。从中找出所有和 = 0的3个数的组合。如果没有这样的组合,输出No Solution。如果有多个,按照3个数中最小的数从小到大排序,如果最小的数相等则按照第二小的数排序。
Input
第1行,1个数N,N为数组的长度(0 <= N <= 1000)
第2 - N + 1行:Aii(-10^9 <= Aii <= 10^9)
Output
如果没有符合条件的组合,输出No Solution。
如果有多个,按照3个数中最小的数从小到大排序,如果最小的数相等则继续按照第二小的数排序。每行3个数,中间用空格分隔,并且这3个数按照从小到大的顺序排列。
Sample Input
7
-3
-2
-1
0
1
2
3
Sample Output
-3 0 3
-3 1 2
-2 -1 3
-2 0 2
-1 0 1
自从用了vector,能不开数组,再也不开数组啦>v<
#include<bits/stdc++.h>
using namespace std;
struct nod{ //定义一个结构体
int a;
int b;
int c;
};
int cmp(nod a,nod b){
if(a.a ==b.a){
if(a.b==b.b){
return a.c<b.c; //按升序,排序结构体的三个数
}return a.b<b.b;
}return a.a<b.a;
}
vector<int> v;
vector<nod> s;
int main(){
int i,j,n; //要求的是a+b+c=0; 改为求是否存在-a =b+c
int k,sum;
nod g;
while(cin>>n){
for(i=0;i<n;i++){
cin>>k;
v.push_back(k); //所有数据保存到数组v里面
}
sort(v.begin(),v.end()); //数据排序(升序)
for(i=0;i<n;i++){
sum=-v[i]; //取数组元素,原来是a,这里我们需要的是-a;
int l=i+1,r=n-1; //二分搜索
while(l<r){
if(v[l]+v[r]==sum){
g.a=v[i]; g.b=v[l]; g.c=v[r]; //假如b+c==-a;
s.push_back(g); //把这组b,c,a,存入s数组(借助一个中间结构体变量g)
}
if(v[l]+v[r]<sum) //假如b+c<-a; 说明左边的数需要再大一点
l++; //左坐标右移(l++),如-3 + 2 < 0 ,, -3的右边一位是比-3大的数,右移才可能找到解
else
r--; //一样的,b+c>-a;说明右边的数需要小一点,
} //右坐标左移(r--),如 -2 + 3 > 0 ,, 3的左边一位是比3小的数,左移才可能找到解
}
if(!s.empty()){ //判断一下,s非空再进行输出
sort(s.begin(),s.end(),cmp);
for(i=0;i<s.size();i++){
cout<<s[i].a<<" "<<s[i].b<<" "<<s[i].c<<endl;
}
}
else
cout<<"No Solution"<<endl;
}
return 0;
}