一个面试题，大家评评理

[gps949]

这两天去水了个面试，瞎写了一段代码，姑且不论这段代码能不能实现目标，面试现场 N 个面试官一位很牛逼哄哄地说：这个按理说 O(n)就可以了，你这两个遍历，都 O(n^2)了。
我简单解释两句说内层并不是完整遍历而是在计算连续 0 的长度后会把外层指针 i 移动过这一段，所以本质上还是近似算 O(n)的。
然后那个面试官又一脸不屑的说：你这两层遍历再怎么也不会是 O(n)，最多算 O(logn)，你回去再好好想想。
然后我无奈：好的。

下面是代码（只是近似，毕竟也没带出来材料）

a=[1,0,1,0,0,0,1,0,0,1,1,1,0,0,0,0,1,0,1,0]
for (i=0;i<a.length;i++) {
    if (a[i]==0) {
        j=i+1;
        for (;j<a.length && a[j]==0;j++) {}
    
        //此处省略一通利用 i 和 j 的判断运算（没有对 i 或 j 的值的改变，也没有任何循环）
    
        i=j+1
    }
}

[yuruizhe]

前后双指针，是 O(n)

[yuruizhe]

@lixiang2017 居然能看出题目原意是“找出所有的 0”，那感觉一个 for 就够了…

[lixiang2017]

@yuruizhe 嗯，一层循环就行，用个变量记录之前的下标，满足一定条件就去处理数据或更新下标。