1393 0和1相等串

給定一個0-1串，請找到一個盡可能長的子串，其中包含的0與1的個數相等。

收起

輸入

一個字元串，隻包含01，長度不超過1000000。
           

輸出

一行一個整數，最長的0與1的個數相等的子串的長度。
           

輸入樣例

1011
           

輸出樣例

2
           

我發現腦洞一定要大，越大越好，不然有些辦法你想不出來，

如果0和1的個數相等，我們要做的事情就是找到最長的區間[i+1~j]：使得s[i]==s[j];

那麼我們設定一個數組a[i]表示數值i出現的最左端的位子，但是這麼設定顯然不行，因為可能有負數的情況，那麼對應設定一個mid（這也就是為什麼是1003000的原因），表示其為0，那麼-1出現的最左端的位子就是a[mid-1]，我們在過程中維護最大值即可，注意：10/01/0000001這樣類似的情況。

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<math.h>

#include<set>

#include<stack>

#include<queue>

#include<string>

#include<iostream>

#include<vector>

using namespace std;

int a[2006000];

char s[2006000];

int main()

{

    scanf("%s",s+1);

    memset(a,-1,sizeof(a));

    int mid=1003000,ans=0,num1=0,num0=0;

    int l=strlen(s+1);

    a[mid]=0;

    for(int i=1; i<=l; i++)

    {

        if(s[i]=='1')

            num1++;

        else num0++;

        int sum=num0-num1;

        if(a[mid+sum]==-1)

        {

            a[mid+sum]=i;

        }

        ans=max(ans,i-a[mid+sum]);

    }

    printf("%d\n",ans);

    return 0;

}