给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组连续的。

重复出现（不同位置）的子串也要统计它们出现的次数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-binary-substrings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

前缀和

import java.util.Scanner;

class Solution {

    private int getOneNum(int[] dp, int left, int right) {
        return left == 0 ? dp[right] : dp[right] - dp[left - 1];
    }

    private int getZeroNum(int[] dp, int left, int right) {
        return right - left + 1 - getOneNum(dp, left, right);
    }

    public int countBinarySubstrings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int sum = 0;
        int one = 0, zero = 0;
        int ans = 0;
        int[] dp = new int[s.length()];
        for (int i = 0; i < s.length(); ++i) {
            sum += s.charAt(i) - '0';
            dp[i] = sum;
            if (s.charAt(i) == '0') {
                one = 0;
                zero++;
                if (i - 2 * zero + 1 >= 0 && getOneNum(dp, i - 2 * zero + 1, i) == zero) {
                    ans++;
                }
            } else {
                one++;
                zero = 0;
                if (i - 2 * one + 1 >= 0 && getZeroNum(dp, i - 2 * one + 1, i) == one) {
                    ans++;
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().countBinarySubstrings("00110011"));
    }
}

前缀和（优化）

class Solution {
    public int countBinarySubstrings(String s) {
        int ptr = 0, n = s.length(), last = 0, ans = 0;
        while (ptr < n) {
            char c = s.charAt(ptr);
            int count = 0;
            while (ptr < n && s.charAt(ptr) == c) {
                ++ptr;
                ++count;
            }
            ans += Math.min(count, last);
            last = count;
        }
        return ans;
    }
}