题解 | #未排序数组中累加和为给定值的最长子数组系列问题补1#前缀和

#include <iostream>
#include <unordered_map>
using namespace std;
int n,presum,a[100005],st,ma;
unordered_map<int,int>hmap;
int main() {
    cin>>n;
    for(int i=0;i<n;i++){
        int t;
        scanf("%d",&t);
        if(t>0)a[i]=1;//正负转化为1，-1，正数与负数个数相等转化为和为0
        else if(t<0)a[i]=-1;
        else a[i]=0;
    }
    hmap.insert({0, -1});
    for(int i=0;i<n;i++){
        presum+=a[i];
        if(hmap.find(presum)!=hmap.end()){
            st=hmap[presum];
        ma=max(ma,i-st);
        }
        else hmap.insert({presum,i});
    }
    cout<<ma;
}

题目4【算法讲解046【必备】构建前缀信息的技巧-解决子数组相关问题】 https://www.bilibili.com/video/BV1Sj411q7fi/?share_source=copy_web&vd_source=5065fa61022691e8df35c771a30e6d29