均衡题解

【前言】
非常简单的题目。
【暴力】
枚举起点和终点即可。
复杂度O(n^2)
【正解】
我们把0看成-1，然后求出前缀和数组s[]，可以发现，如果区间[i,j]满足条件，那么s[j]-s[i-1]=0，即s[j]=s[i-1]，那么对于每个s[]中可能的取值，保留最前面的那一个，用来更新答案即可。
用桶来实现。
复杂度O(n)

参考代码：

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @param aLen int a数组长度
     * @return int整型
     */
    int fre[300000];
    int wwork(int n, int* a, int aLen) {
        // write code her
        int ans=0,x=0;
       scanf("%d,[",&n);
       for (int i=1;i<=n;i++)
       {
              int t;
              t=a[i-1];
              if (t==0) x-=1;
              else x+=1;
              if (x==0) {ans=max(ans,i); continue; }
              if (fre[x+100005]==0) fre[x+100005]=i;
              else ans=max(ans,i-fre[x+100005]);
       }
       return ans;
    }
};