相等的和

题目 相等的和

思路分析

想到了第一层 其实就快出来了 但因为对哈希的本质还没有理解深刻 导致差一点点……

一开始从暴力的想删除某个元素肯定是不可能的

后面想到可以求出 各个序列里 缺少某个值 的和 的集合出来

然后比对一下几个集合里是否存在一样的元素即可

错在我选错了key 开了多个哈希表 把删除的元素的下标做了key 显然是浪费了哈希表的作用 对于两个序列的情况是有用的 但是序列一多 4 5个的话 就成了4 5层循环 失败

选key的时候要选择判重的元素为key 这个很关键 附加的信息存才在val里

像这里关键的就是那个缺少某个元素后的总和 它才是key 附加的它属于哪个序列 是第几个元素才是val

我们只需要判断后面计算出的缺少某一个元素的总和是否在哈希表里出现过 若出现过 且不是一个序列的 就输出两个信息即可

代码实现

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N=2e5+10;

int a[N];

unordered_map<int,PII> h;

int k;

int main()

{

    cin>>k;

    for(int T=1;T<=k;T++){

        int l;

        cin>>l;

        int sum=0;

        for(int i=1;i<=l;i++){

            cin>>a[i];

            sum+=a[i];

        }

        for(int i=1;i<=l;i++){

            int t=sum-a[i];

            if(h.count(t) && h[t].first!=T){

                puts("YES");

                cout<<h[t].first<<" "<<h[t].second<<endl;

                cout<<T<<" "<<i;

                return 0;

            }

            h[t]={T,i};

        }

    }

    puts("NO");

    return 0;

}

同类题型

视频讲解

⬅️ 电话号码 🏠 00-刷题理模型 ➡️ 矩阵