给定一个0-1串，请找到一个尽可能长的子串，其中包含的0与1的个数相等。

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1393

这题解法很奇妙。也是看了别人的思路才想出来.

首先考虑把0全部变成-1。然后统计一个前缀和,用sum[i]表示.

那么从起点开始的子串是合法的只要sum[i]的值等于0即可.

如果子串起点不为0,那么只要两次出现sum[i],这两个数值之间一定是合法的子串.

例如:

标号： 1 2 3 4 5

数值 0 0 1 1 0

sum -1 -2 -1 0 -1

i==4的时候sum[i]==0,所以1-4之间是一个合法的子串,长度为4

sum[1]==sum[3]==sum[5]== -1,所以 (1,3],(1,5],(3,5]之间都是合法的子串,取最大值也是4.

我是用了map,其实不用这么麻烦,只要用一个变量就可以代替sum数组,并且另外开一个标记数组可以代替map做映射.

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 #include <map>
 5 using namespace std;
 6 char s[1000010];
 7 int t[1000010],sum[1000010];
 8 int main()
 9 {
10     //freopen("a.txt","r",stdin);
11     scanf("%s",s+1);
12     int l=strlen(s+1);
13     for(int i=1;i<=l;i++)
14         if(s[i]=='0') t[i]=-1;
15         else t[i]=1;
16     //for(int i=0;i<l;i++) printf("%d",t[i]);
17     sum[1]=t[1];
18     map<int,int>m;
19     m[sum[1]]=1;
20     int maxn=0;
21     for(int i=2;i<=l;i++)
22     {
23         sum[i]=sum[i-1]+t[i];
24         //printf("%d
",sum[i]);
25         if(m[sum[i]]!=0) maxn=max(maxn,i-m[sum[i]]);
26         else m[sum[i]]=i;
27         if(sum[i]==0) maxn=max(maxn,i);
28     }
29     printf("%d
",maxn);
30     return 0;
31 }