算法1

(暴力枚举) $O(n^3)$

就是结结实实的枚举，时间复杂度太高，过不了

时间复杂度

参考文献

java 代码

class Solution {
    int count=0;
    public int countBinarySubstrings(String s) {
        for(int i=0;i<s.length();i++){
            for(int j = i+1;j<s.length();j++){
                if(isSuit(i,j,s)) {count++;System.out.println(i+"-"+j);}
            }
        }
        return count;
    }
    public boolean isSuit(int i, int j, String s){
        //0和1的个数是否相同，相同的元素是否相邻；
        if((j-i+1)%2==1) return false;
        //一定是前面的都是同一个数字，后面的是另一组数字
        char curi = s.charAt(i);
        char curj = s.charAt(j);
        while(j>i)
        {
            if(s.charAt(i)!=s.charAt(j)&&s.charAt(i)==curi&&s.charAt(j)==curj) {i++;j++;continue;}
            else return false;
        }
        return true;
    }
}

算法2

(还是比较暴力枚举) $O(n^2)$

解的形式是全是偶数，然后前一半是同一个数字，后一半是另一个数字
思路：直接在字符串里面搜后和后一个数字有变化的数字，才可以作为解的最中间的部分，然后向两边枚举，找出所有解的形式；

时间复杂度

参考文献

java 代码

class Solution {
    int ans=0;
    public int countBinarySubstrings(String s) {
        //找到以i为中心的解
        for(int i =0;i<s.length()-1;i++){
            if(s.charAt(i)!=s.charAt(i+1))//就一定存在解了，就是计算解的个数
            {
                count(i,s);
            }
        }
        return ans;
    }
    public void count(int l ,String s)//以i为中点的解的个数
    {
        int r =l+1;
        for(int i=l,j =r;i>=0&&j<s.length();i--,j++){
            if(s.charAt(i)==s.charAt(l)&&s.charAt(i)!=s.charAt(j)) ans++;
            else break;
        }

    }
}

算法2

(官方) $O(n)$

比如‘00110110’，将它存为[2,2,1,2,1],是连续相等数的个数,满足条件的值就是新数组相邻数之间最小数的和；

java代码

class Solution {
    public int countBinarySubstrings(String s) {
        //双指针的存进去的方法
        int i =0,j=0;
        ArrayList<Integer> ml = new ArrayList<>();
        while(j<s.length()){
            while(j<s.length()&&s.charAt(j)==s.charAt(i)) j++;
            ml.add(j-i);
            i=j;
        }
        int count=0;
        i=0;
        while(i<(ml.size()-1)){
            count+=Math.min(ml.get(i),ml.get(i+1));
            i++;
        }
        return count;
    }
}

算法2

(官方改进) $O(n)$

由于比较的时候只是用到当前值和前一个值，可以将状态值维护到两个变量中，将空间复杂度降到O(1)，

java代码

class Solution {
    public int countBinarySubstrings(String s) {
        //双指针的存进去的方法
        int i =0,j=0;
        int pre=0;
        int cur=0;
        int count=0;
        while(j<s.length()){
            while(j<s.length()&&s.charAt(j)==s.charAt(i)) j++;
            cur=j-i;
            count+=Math.min(pre,cur);
            pre=cur;
            i=j;
        }
        return count;
    }
}