题意:在只有0 1 的字符串中,找到最大区间值使得0和1的个数相等
题解:可以利用前缀和1 则sum++,0则sum--,在之后遇到相同的sum值时,减去之前出现该sum的最小下标,然后更新答案,即可。
#include using namespace std;typedef long long ll;typedef long double db;typedef pair pii;typedef vector vi;#define de(x) cout << #x << "=" << x << endl#define rep(i,a,b) for(int i=a;i<(b);++i)#define all(x) (x).begin(),(x).end()#define sz(x) (int)(x).size()#define pb push_back#define fi first#define se secondconst int N = 1e5+5;map mp;char str[N];int main(){ int n; int sum=0,ans=0; scanf("%d",&n); scanf("%s",str+1); mp[0]=0; for(int i=1;i<=n;i++) { if(str[i]=='1') sum++; else sum--; if(mp.count(sum)) { ans=max(ans,i-mp[sum]); } else mp[sum]=i; } cout< <