题目:
总结大佬们的思路:
思路1:所有数两两求和,存入map中,每次判断有没有相反数被标记过。
思路2:对所有数排序,排完所有数两两求和,结果正好是排好序的。然后扫一遍,二分查找看之前有没有相反数存在。
思路1时间复杂度O(n^2),空间复杂度O(n^2)
思路2时间复杂度O(n^2log(n)),空间复杂度O(n^2)
两个都可以过,不卡时间。
要注意的一点是,要标记是哪两个数的和。
否则可能会重复计算某个数,这就不是四个数的和为0了。
代码:
#include <bits\stdc++.h>
using namespace std;
typedef long long ll; //l表示较小的索引,r表示较大的索引
//用来判断是否重复
struct node{
int l;int r;
}; int a[];
map<ll,node> m; int main() {
int n;
cin >> n;
for(int i = ;i < n; i++){
cin >> a[i];
}
for(int i = ;i < n; i++){
for(int j = i+;j < n; j++){
ll k = a[i]+a[j];
//如果m[-k](当前和的相反数)没有被标记过
if(m[-k].l != ||m[-k].r != ){
//如果m[-k]不重复
if(m[-k].l != i && m[-k].r != i && m[-k].l != j && m[-k].r != j){
cout << "Yes" << endl;
return ;
}
}
node x;
x.l = i;x.r = j;
m[k] = x;
}
}
cout << "No" << endl;
return ;
}
// writen by zhangjiuding
虽然代码过了,但是有一种情况没有考虑到,可能是数据比较弱。
就是m[k]可能要存多组不同的索引,代码起码要增加十几行。