Given a binary string of length N and an integer K, we need to find out how many substrings of this string are exist which contains exactly K ones.
Examples:
Input : s = “10010”
K = 1
Output : 9
The 9 substrings containing one 1 are,
“1”, “10”, “100”, “001”, “01”, “1”,
“10”, “0010” and “010”

static int countOfSubstringWithKOnes( 
                            String s, int K) 
    { 
        int N = s.length(); 
        int res = 0; 
        int countOfOne = 0; 
        int []freq = new int[N+1]; 

        freq[0] = 1; 

        for (int i = 0; i < N; i++) { 
            countOfOne += (s.charAt(i) - '0'); 
            if (countOfOne >= K) { 
                res += freq[countOfOne - K]; 
            } 
            freq[countOfOne]++; 
        }   
        return res; 
    } 

注意：求子串的時(shí)候，尤其是涉及長(zhǎng)度，子串里面元素個(gè)數(shù)之類的問(wèn)題，可以用類似于動(dòng)態(tài)規(guī)劃的方法，用當(dāng)前遍歷的值減去之前的值，來(lái)找子串，實(shí)現(xiàn)復(fù)雜度O(n)。
相似的問(wèn)題：https://www.geeksforgeeks.org/longest-substring-with-count-of-1s-more-than-0s/