题目是这样的，在一个数组中只有0和1，要求输出所有的相邻的0和1数目相同的区间的起始位置，时间复杂度尽量好（要求是O(n)）
例如：
数组a：{0,1,1,1,0,0,1,0}
输出：(0, 1)   (0, 5)   (0, 7)   (2, 5)   (2, 7)   (3, 4)   (3, 6)   (5, 6)   (6, 7)  (输出的先后顺序可能不同）
结果（0,5）表示a[0]和a[5]间0和1的数目相等都为3.

[ 本帖最后由 wenxinwukui 于 2011-6-9 20:32 编辑 ]

首先，复杂度不可能是O(n)
而是O(n^2)
因为给你一组0,1,0,1,0,1,0,1,0,1......,0,1
光答案就有O(n^2)个，输出都要那么多

假设长度是n
for(delt[0]=0,i=1;i<=n;i++) delt[i]+=delt[i-1]+(a[i-1]?1:-1);
for(i=0;i<=2*n;i++) headg[i]=-1;
for(i=0;i<=n;i++){
    l[i]=headg[delt[i]+n];
    headg[delt[i]+n]=i;
}
for(i=0;i<=2*n;i++){
    for(k=0,j=headg[i];~headg[i];k++,j=l[i]) q[k]=j;
    for(j=0;j<k;j++) for(l=j+1;l<k;l++) printf("(%d,%d) ",q[j],q[l]);
}
printf("\n");

谢谢。这个题是一个面试题，我当时写出来了O(n^2)的算法，不过面试官说有O(n)的让我想，我没有想出来，所以在这求教各位了。