题目： 给你一个长度为n的字符串，字符串只包含0和1，找一个最长的子串，要求这个子串的0的个数等于1的个数，输出最大长度
第一行输入字符串的长度n，1<=n<=100000.第二行输入字符串s.
输出满足条件的最大子串长度，如果不存在这样的子串，输出0
Input 8 11010111 Output 4 Input 3 111 Output 0
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int N = 1e5 + 10; int n,sum[N],first[2 * N],ans; // 因为前缀和记录的是差值，所以可能会有负数出现，所以记录前缀和第一次出现位置的first数组要在[N,2N]的范围内取值 char s[N]; int main(void) { cin >> n; cin >> s + 1; for(int i = 1 ; i <= n ; i++) { // 求1到n的前缀和（1的权值为1，0的权值为-1），前缀和数组中相当存储的是1比0多的个数 sum[i] = sum[i - 1] + (s[i] == '1' ? 1 : -1 ); } for (int i = 1 ; i <= n ; i++) { // 1 2 3 4 5 6 7 8 // 1 1 0 1 0 1 1 1 // 1 2 1 2 1 2 3 4 if(sum[i] == 0) { ans = i; } if (first[sum[i] + n] != 0 && sum[i] != 0) // 如果这个前缀和是第二次出现 （则中间一定会有一段是0和1互相抵消的字符串） { // 要特别判断当1和0的个数完全相等的时候 这个时候复合要求的字段的长度就是当前的位置（且此时这个字段覆盖了目前 // 从头开始的所有字符，则一定会比当前的ans长，所以直接赋值即可） // i - first[sum[i] + n] 就是包含当前位置的这一段复合要求的字段长度 ans = max(ans,i - first[sum[i] + n]); } if (first[sum[i] + n] == 0 && sum[i] != 0) // 这个前缀和是第一次出现的话（也要特判 0 ，0无论是不是第一次出现都会导致一段符合的目前最长字段出现） { first[sum[i] + n] = i; // 记录这个第一次出现的字段的位置 } } cout << ans << endl; return 0; }