51nod 1267 4个数和为0 思路：哈希map+避免重复的点

题目：

总结大佬们的思路：

思路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]可能要存多组不同的索引，代码起码要增加十几行。

巴特西

51nod 1267 4个数和为0 思路：哈希map+避免重复的点

最新文章

热门文章