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

题目描述：

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

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

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

 

最简单的想法就是遍历所有的子串，之后判断该子串是否满足条件N^2子串，每个子串扫一遍判断0、1是否出现的次数相等，复杂度为O(N^3)

 

方法一：
稍加思考就会发现， 如果一个长度为n的子串满足条件，加么这n个元素的和加起来一定=(n/2),且
子串长度为偶数，这样在循环的过程中，增量加就可以了，不需要每个子串从头计算，复杂度降为O(N^2).
该思想的程序为fun():

 

 

int fun(char num[],int n)
{
    int i,j;
    int maxlen=0;//所求
    int sum,currentlen;//当前子串和与当前子串长度
   //挨个判断每个子串是否符合要求，若符合，则更新maxlen
   for(i=0;i<n;i++)
    {
       sum=0;
       for(j=i;j<n;j++)
       {
           currentlen = j-i+1;
          sum+=num[j]-'0';
          if(currentlen%2==0 && sum==currentlen/2 && currentlen>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<n;i++)
   {
       sum=0;
       for(j=i;j<n;j++)
       {
           currentlen = j-i+1;
           if(num[j]=='0')
               sum--;
           else
               sum++;
           if(sum==0 && currentlen>maxlen)
               maxlen = currentlen;
       }
   }
   return maxlen;
}
方法三：
一种巧妙的解法：定义一个数据temp[N]， temp[i]表示从num[0...i]中 num_of_0 - num_of_1，0的个数与1的个数的差那么如果num[i+1] ~ num[j]是符合条件的子串，一定有 temp[i] == temp[j]，因为中间的部分0、1个数相等，相减等于0。只需要扫一遍num[N]就能把temp[N]构造出来了。这样问题就转换成了求距离最远的一对数，使得temp[i] == temp[j]，因为temp[i]的范围一定是[-N,N]，-N到N的范围所对应的从num[0]开始的子串的结尾下标i都存起来，这样每扫到temp[i]，查数就行了。
 
 
设两个辅助数组temp[]与assist[]，代表的意义如下:
temp[i]表示num[0...i]中0的个数与1的个数差(即0的个数减去1的个数),则必有 -n<=temp[i]<=n
 
assist[]为辅助数组，里面存了0,1个数差所对应的num的最小下标，初值为-1表示该处还未存入内容。
assist[0]表示0,1个数差为-n的从num[0]开始的子串的结尾位置，即num[0...i]中的i，此时num[0...i]串中0,1个数差为-n,assist[2*n]表示0,1个数差为n的从num[0]开始的子串的结尾位置，即num[0...i]中的i，此时num[0...i]串中0,1个数差为n,assist[k]表示0,1个数差为 k-n 的从num[0]开始的子串的结尾位置。即assist[k+n] = i 表示0,1个数差为k的子串为num[0...i]
  
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<n;i++)
    {
       count[num[i]-'0']+=1;
       temp[i] = count[0]-count[1];
       if(assist[temp[i]+n]==-1)  //还不存在0,1个数差为temp[i]的从num[0]开始的子串
          assist[temp[i]+n] = i;
      //已存在0,1个数差为temp[i]的从num[0]开始的子串，设assist[temp[i]+n]为k,则该子串为num[0..k]
       else        
       {
   //设assist[temp[i]+n]为k，从num[0...i]中去掉num[0...k]为当前找到的符合条件的子串
           currentlen = i- assist[temp[i]+n]; 
          if(currentlen > 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<Integer, Integer> map = new HashMap<Integer, Integer>();
		map.put(0, 0);
		int begin = 0;
		int max = 0;
		int current = 0;
		for(int i=0; i<input.length; i++){
			if(input[i] == 0){
				current--;
			}else{
				current++;
			}
			Integer p = map.get(current);
			if(p == null){
				map.put(current, i+1);
			}else{
				int l = p.intValue();
				if((i+1-l) > max){
					max = i + 1 - l;
					begin = l;
				}
			}
			
		}
		for(int j=begin; j<begin+max; j++){
			System.out.print(input[j]);
		}
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
//		int[] input = {0,1,1,0,0,1,1,1};
		int[] input = {1,0,0,0,0,0,1,1};
		ZeroOnePairs.find(input);
 
	}
 
}

 

参考文献

https://blog.csdn.net/c_circle/article/details/78589130 

http://blog.sina.com.cn/s/blog_3f297c5c0101aupu.html、