01 相等的串

给定一个 01 串,求它一个最长的子串满足 0 和 1 的个数相等

分析

  • 把 0 看成 -1,1 当做 +1,使用前缀和
  • 需要两个前缀和相等,则这两个前缀和之间的子串满足 0 的个数和 1 的个数相等。
  • 对前缀和排序?O(nlogn)
  • 优化——不需要排序
    • 前缀和范围是[-n..n],我们加上 n 之后就是[0..2n],只要记录每个和第一次出现的位置
    • 本质是利用 hash 代替排序
    • 当 hash 值是比较小的非负整数时,可以用作数组下标
int run(char *s){
    int n = strlen(s);
    // 开一个长度为 2n + 1 的数组 (n << 1) | 1 ,并设为 -1
    vector<int> have((n << 1) | 1, -1);
    // 因为是从 n 开始,
    have[n] = 0;
    int sum = n;
    int best = 0;
    for (int i = 0; i < n; i++){
        sum += (s[i] == '0') ? (-1):(+1);
        if (have[sum] >= 0){
            best = max(best, i - have[sum] + 1);
        } else {
            have[sum] = i + 1;
        }
    }
}

方法比较 tricky,需要注意细节。