大致题意：
输入整数n（1<=n<=100000)，再输入由n个0或1组成的字符串，求该字符串中满足1和0个数相等的最长子串、子序列。
sample input：
8
01001001
sample output：
4 6
题解：
补充一下子串和子序列的区别：字串必须连续，子序列不必连续。
求01个数相等的最长子序列长度：min（0的个数，1的个数）。
下面说求01个数相等的最长子串长度：
可以建一个sum数组求前缀和，因为要使0和1个数相等，所以0可以用-1代替，故当sum[r]-sum[l-1]=0时区间[l,r]则为满足01个数相等的子串，此时求出l-1和r的差值即为满足条件的子串长度，不断更新结果求最大长度。
但是到这一步后起初想到的做法是两重循环枚举更新最大差值，这样会超时。
O(n)做法：建一个flag数组记录不同前缀和第一次出现的下标位置（也可用map记录），后面找到相同前缀和时则更新两者位置的差值，这样扫一遍就可以了。（注意：当前缀和sum[r]=0时，r即为满足条件的子串长度）
官方题解如下：
Code：
/*5ms*/
#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false);
using namespace std;
const int MAX=1e5+;
char s[MAX];
int n,sum[MAX],flag[*MAX],max1;
int main()
{
IO;
while(!(cin>>n>>s+).eof())
{
memset(flag,-,sizeof(flag));
int ans1=,ans0=;
for(int i=;i<=n;i++){
if(s[i]=='')ans0++,sum[i]=sum[i-]-;
else ans1++,sum[i]=sum[i-]+;
if(flag[MAX+sum[i]]==-)flag[MAX+sum[i]]=i;
else max1=max(i-flag[MAX+sum[i]],max1);
if(sum[i]==)max1=max(max1,i);
}
cout<<max1<<' '<<*min(ans1,ans0)<<endl;
}
return ;
}
或者用STL的map实现，代码如下：
/*52ms*/
#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false);
using namespace std;
map<int,int>m;
int main()
{
IO;char c;int n;
while(!(cin>>n).eof())
{
int ret=,ans1=,sum=;
m.clear();m[]=;
for(int i=;i<=n;++i){
cin>>c;
if(c=='')ans1++,sum++;
else sum--;
if(m.count(sum))ret=max(ret,i-m[sum]);//map.count(Key)返回值为1或者0，1返回存在，0返回不存在
else m[sum]=i;
}
cout<<ret<<' '<<*min(ans1,n-ans1)<<endl;
}
return ;
}