CodeForces

Balanced Substring

题目大意

给定一个字符串, 字符串中只含有 0 和 1, 求一个区间 [l, r] 内, 0 和 1 数量相等的最大子串.

思路

这道题的字符串最大长度为 100000, 若使用 O(n) 的算法肯定会超时, 所以需要使用 前缀和 进行求值.

对于prefixSum(初始化为100100, 防止负数导致下标越界) 将 0 处理为 -1, 1 处理为 +1 操作;

一个 last 数组保存 一个前缀和 的 第一次出现的位置. 不断更新 ans数组, 需要注意的是 last[0] = 0; 因为当数组长度为 0 时, 前缀和为 0, 这样可以防止答案为整个数组长度时.

代码

#include <cstdio>
#include <cstring>
#define MAXN 200200
#define MOVL 100100
using namespace std;
int last[MAXN];
int ans[MAXN];
int max(int a, int b){
    return a > b ? a : b;
}
int main(){
    int nNum;
    scanf("%d
", &nNum);
    char c;
    int fi = 0, prefixSum = MOVL;
    memset(last, -1, sizeof(last));
    last[0 + MOVL] = 0;
    for(int i = 1; i <= nNum; i++){
        int val = getchar() - '0';
        if(val == 0) val = -1;
        prefixSum += val;

        if(last[prefixSum ] == -1)
            last[prefixSum ] = i;
        else
            ans[prefixSum] = i - last[prefixSum];
        fi = max(fi, ans[prefixSum]);
    }
    printf("%d", fi);
    return 0;
}