描述
题解
前缀和+Hash记录,复杂度为O(N)。这里需要强调的是要考虑到01
这种最长的情况是打头开始的串,所以需要对dif[MAXN] = 0;
初始化。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 1e6 + 10;
const int INF = 0x3f3f3f3f;
char S[MAXN];
int SUM[MAXN] = {
0}; // 0化作-1
int dif[MAXN * 2];
int main(int argc, const char * argv[])
{
memset(dif, 0x3f, sizeof(dif));
dif[MAXN] = 0;
scanf("%s", S + 1);
int len = (int)strlen(S + 1);
int ans = 0;
for (int i = 1; i <= len; i++)
{
if (S[i] == '0')
{
SUM[i] = SUM[i - 1] - 1;
}
else
{
SUM[i] = SUM[i - 1] + 1;
}
if (dif[SUM[i] + MAXN] == INF) // 防止下标越界
{
dif[SUM[i] + MAXN] = i;
}
else
{
ans = max(ans, i - dif[SUM[i] + MAXN]);
}
}
cout << ans << '\n';
return 0;
}