本文共 2240 字，大约阅读时间需要 7 分钟。

原文地址：

已知一个字符串，这个字符串只包含0,1,2，求子字符串的数目，这些子字符串包含有相同数目的0,1,2。

例子：

输入:  str = “0102010”输出:  2解释: 子字符串str[2, 4] = “102” 与子字符串str[4, 6] = “201”有相同数目的0, 1和2输入: str = "102100211"输出: 5

一个简单的方法就是迭代出str的所有子字符串，然后检查是否有相同数目的0,1,2。str字符串的子字符串的数目有O(${n^2}$)，检查每一个子字符串的时间需要花费O(n)。所以用暴力法解决这个问题需要花费的总时间是 O(${n^3}$)。

计算0,1,2数目的一个有效的方法

设zc[i]表示下标在1到i之间的0的数目  oc[i]表示下标在1到i之间的1的数目  tc[i]表示下标在1到i之间的2的数目对于将要被计入结果的子字符串str[i, j]我们应该有:    zc[i] – zc[j-1] = oc[i] – oc[j-1] = tc[i] - tc[j-1]我们可以把上面的式子写成下面这样:z[i] – o[i] = z[j-1] – o[j-1]   与z[i] – t[i] = z[j-1] – t[j-1]

在循环字符串的过程中可以追踪上面的关系，在每一个下标i上我们将计算这个不同的对，我们将要检查不同的对在前面发生的次数，并且把这个次数加到结果中，在下面的代码中我们用map对前面的差异进行跟踪。考虑到对map的操作，这个方法的总时间复杂度O(nlogn) ，比如查询和插入需要花费的时间是O(Log n)。

// C++ program to find substring with equal// number of 0's, 1's and 2's#include 
   
    using namespace std;// Method to count number of substring which// has equal 0, 1 and 2int getSubstringWithEqual012(string str){    int n = str.length();    // map to store, how many times a difference    // pair has occurred previously    map< pair
    
     , int > mp;    mp[make_pair(0, 0)] = 1;    //  zc (Count of zeroes), oc(Count of 1s)    //  and tc(count of twos)    //  In starting all counts are zero    int zc = 0, oc = 0, tc = 0;    //  looping into string    int res = 0;  // Initialize result    for (int i = 0; i < n; ++i)    {        // incresing the count of current character        if (str[i] == '0') zc++;        else if (str[i] == '1') oc++;        else tc++;  // Assuming that string doesn't contain                    // other characters        // making pair of differences (z[i] - o[i],        // z[i] - t[i])        pair
     
       tmp = make_pair(zc - oc,                                       zc - tc);        // Count of previous occurrences of above pair        // indicates that the subarrays forming from        // every previous occurrence to this occurrence        // is a subarray with equal number of 0's, 1's        // and 2's        res = res + mp[tmp];        // increasing the count of current difference        // pair by 1        mp[tmp]++;    }    return res;}//  driver code to test above methodint main(){    string str = "0102010";    cout << getSubstringWithEqual012(str) << endl;    return 0;}
     
    
   

输出：

2

转载地址：http://nzhii.baihongyu.com/