Zeratul有一个长度为n的字符串，字符串只包含0和1两种字符。 现在他想知道，这个字符串中有多少非空子串满足“0和1两种字符的个数相等”。

算法1：

暴力枚举

对于每个子串都判断一遍是否满足条件，时间复杂度O(n^3)。

算法2：

前缀和

对于每一个位置i，维护一个前缀和p[i]表示从1~i中0的个数减去1的个数。如果有一个子串s[l,r]满足0和1的个数相等，那么有p[r]-p[l-1]=0。因此我们可以枚举左右端点，然后计算前缀和之差是否为0。时间复杂度O(n^2)。

算法3：

哈希

我们可以将0视为-1，将1视为1，那么0和1个数相等的子串就是和为0的子串。因此我们可以维护一个前缀和q[i]表示从1~i的和，然后对于每个位置i，我们在之前出现过的所有位置中查找是否有一个位置j，使得q[i]-q[j]=0，如果有，那么i和j之间的子串就是一个满足条件的子串。我们可以用哈希表来维护之前出现过的每个前缀和所对应的位置。时间复杂度O(n)。

C++ 代码

相关问题

Zeratul有一个长度为n的字符串，字符串只包含0和1两种字符。 现在他想知道，这个字符串中有多少非空子串满足“0和1两种字符的个数相等”。代码

### 回答1：
思路：

对于一个子串，若其中0和1两种字符的个数相等，则其可以表示为“01”，“10”，“0101”，“1010”等形式，即0和1的交替出现。因此，我们可以遍历字符串，记录当前0和1的个数差，若当前差值为0，则说明找到了一个符合要求的子串。

具体地，我们可以维护一个计数器diff，表示当前0的个数减去1的个数，然后遍历字符串，对于每个字符，若是0，则将diff加1，若是1，则将diff减1。若此时diff为0，则说明找到了一个符合要求的子串。

代码：

### 回答2：
这是一个求解非空子串个数的问题。我们可以采用双层循环来解决。

首先，我们需要遍历字符串的每一个字符，作为子串的起始位置。然后，我们再从起始位置开始遍历到字符串结尾的位置，作为子串的结束位置。

在每一次遍历中，我们需要统计子串中0和1两种字符的个数。为了简化问题，我们可以使用两个变量来计数，一个变量count0用于统计0的个数，另一个变量count1用于统计1的个数。

在遍历的过程中，如果我们发现0和1两个字符的个数相等，就说明满足题目要求，我们可以将结果加1。

下面是示例代码实现：

def countSubstring(s):
    res = 0
    n = len(s)
    for i in range(n):
        count0 = count1 = 0
        for j in range(i, n):
            if s[j] == '0':
                count0 += 1
            else:
                count1 += 1
            if count0 == count1:
                res += 1
    return res

s = input("请输入一个只包含0和1的字符串：")
print("非空子串满足“0和1两种字符的个数相等”的个数为：", countSubstring(s))

请注意，这种方法的时间复杂度为O(n^2)，其中n为字符串的长度。如果字符串长度较大，可能会导致运行时间较长。

### 回答3：
算法思路如下：

1. 初始化计数器count=0。
2. 遍历字符串的每个位置i。
3. 再次从位置i开始遍历字符串的每个位置j。
4. 对于位置i到j之间的子串，统计其中0和1的个数。
5. 如果0和1的个数相等，count加1。
6. 返回count作为结果。

代码如下：

def countEqualSubstring(s):
    count = 0
    
    for i in range(len(s)):  # 遍历每个位置i
        zeros = 0
        ones = 0
        for j in range(i, len(s)):  # 从位置i开始遍历每个位置j
            if s[j] == '0':
                zeros += 1
            else:
                ones += 1
            
            if zeros == ones:  # 0和1的个数相等
                count += 1
                
    return count

# 测试样例
s = "00110011"
result = countEqualSubstring(s)
print(result)  # 输出结果为6

以上代码中，通过双重循环遍历所有的子串，并在内层循环中统计0和1的个数，如果个数相等，则计数器count加1。最后返回计数器count作为结果。例如对于字符串"00110011"，有6个满足条件的子串："0011"、"01"、"1100"、"10"、"001100"和"1100"。

Zeratul有一个长度为nn的字符串，字符串只包含0和1两种字符。 现在他想知道，这个字符串中有多少非空子串满足“0和1两种字符的个数相等”。

假设字符串为s，长度为n。我们可以用一个变量cnt来记录当前为止0出现的次数减去1出现的次数的值。如果s的前i个字符的cnt值等于s的前j个字符的cnt值，那么s的第j+1到第i个字符组成的子串就符合条件。

具体地，我们可以使用一个哈希表来记录每个cnt值第一次出现的位置。对于当前处理到的位置i，我们在哈希表中查找cnt值为当前值减去0出现次数与1出现次数差值的位置，如果存在这样的位置j，那么s[j+1:i]就是一个合法的子串。我们统计所有符合条件的子串个数即可。

时间复杂度：O(n)。

代码如下：