【前言】
非常简单的题目。
【暴力】
枚举起点和终点即可。
复杂度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; } };