本文共 2767 字，大约阅读时间需要 9 分钟。

      一个01字符串，求出现0、1出现次数相等的最长子串长度

题目描述：

    已知一个长度为N的字符串，只由0和1组成， 求一个最长的子串，要求该子串出0和1出现的次数相等。

    要求算法时间复杂度尽可能的低。

    比如：  10000010111000001，所求为8，加粗的部分有4个0、4个1  

int fun(char num[],int n){    int i,j;    int maxlen=0;//所求    int sum,currentlen;//当前子串和与当前子串长度   //挨个判断每个子串是否符合要求，若符合，则更新maxlen   for(i=0;i
   
    maxlen)              maxlen = currentlen;       }    }    return maxlen;}
   

方法二：

和fun()的主体差不多，设了一个sum来判断每个子串中0,1个数是否相等，遇到0，sum--；遇到1，sum++。fun()和fun2()求子串的思路和方法要领会，它是以求以每个字符开头的所有子串这样的方式求的，外面再包个大循环就能求出所有子串。

int fun2(char num[],int n){    int i,j;    int maxlen=0;//所求    int sum,currentlen;//当前子串和与当前子串长度   //挨个判断每个子串是否符合要求，若符合，则更新maxlen   for(i=0;i
   
    maxlen)               maxlen = currentlen;       }   }   return maxlen;}
   

int fun1(char num[],int n){    int maxlen=0;//所求    int currentlen;//当前子串长度    int temp[n];    int assist[2*n+1];  //temp[]和assist[]的意义见上    int i;    int count[2]={0,0};//分别代表当前0和1的个数,count[0]为0的个数，count[1]为1的个数   for(i=0;i<2*n+1;i++)       assist[i] = -1;          for(i=0;i
      
        maxlen)              maxlen = currentlen;       }    }    return maxlen;}int main(){    char num[]="10000010111000001";    int maxlen = fun(num,strlen(num));   printf("maxlen=%d\n",maxlen);    return 0;}
      

最后一种解法

/** *  * 数字串，全为0,1组合而成。求一个最长的连续子串，其中0和1的个数相等。 * 比如: 01100111 --> 011001 * 110000011 --> 1100 / 0011 *  * 方法： * 定义一个数组a，a[0] = 0 * 然后遍历输入输入数字串，遇到0，减1，遇到1，加1。含义就是，到目前位置，净值出现了多少个0或者1. * 在数组a中选择两个相等的值，比如都是-3，第一个-3表示到该元素为止，多出现了3个0，第二个-3还是表示 * 到该元素为止，多出3个0，那么这两个元素之间的0和1的个数必定相互抵消。 * 于是，所求子串等同于，数组a中距离最远的两个相同值。可以两次循环，复杂度o(n*n) *  * 为了O(n)的复杂度，利用hash表代替数组。原理一样。 *  **/public class ZeroOnePairs { 	public static void find(int[] input){		HashMap
   
     map = new HashMap
    
     ();		map.put(0, 0);		int begin = 0;		int max = 0;		int current = 0;		for(int i=0; i
     
       max){					max = i + 1 - l;					begin = l;				}			}					}		for(int j=begin; j
     
    
   

参考文献

、