import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        int k=scanner.nextInt();
        scanner.nextLine();
        String s=scanner.nextLine();
        int num=0,len=s.length();
        int[] dp=new int[k+2];
        long result=0;
        dp[0]=1;
        for(char c:s.toCharArray()){
            if(c=='1') num++;
            if(num-k>=0) result+=dp[(num-k)%(k+2)];
            dp[(num+1)%(k+2)]=0;
            dp[num%(k+2)]++;
        }
        System.out.println(result);
    }
}

这是一个子串满足问题，输入一个由0，1字符组成的字符串str，求满足包含k个1的连续字串个数。
毫不夸张的说，可能大部分人第一眼就是求出所有子串，再计数所有满足k的子串，但仔细一想，问题没有那么简单！

思路就是，采用滑动窗口的方式，从字符串数组左侧依次向右滑动，直至满足k个1，在下一个数不为1且数组不越界的情况下窗口向右滑动，同时计数。
核心代码如下：
public class Main {
    public static int NumSubString(int k, String str) {
        char[] chars = str.toCharArray();
        int res = 0;
        int len = chars.length;
        for (int i = 0; i < len; i++) {
            if (chars[i] == '1') {
                res++;
            }
        }
        if (res < k) {
            return 0;
        }
        res = 0;
        for (int i = 0; i < len; i++) {
            /*滑动索引*/
            int index = i;
            int count = 0;
            while (count < k && index < len) {
                if (chars[index] == '1' && ++count == k) {
                    res++;
                    index++;
                    break;
                }
                index++;
            }
            /*满足k后继续右滑*/
            while (index < len && chars[index] != '1') {
                res++;
                index++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        sc.nextLine();
        String str = sc.next();
        System.out.println(NumSubString(k,str));
    }

package 快手2020校园招聘秋招笔试工程C试卷;
import java.lang.*;
import java.util.*;

/**
 * Project: 通过率：100%
 * Author : en_zhao
 * Email  : 
 * Date   : 2020/08/03
 */

public class Main001{
    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        sc.nextLine();
        String str = sc.nextLine();
        //防溢出
        long res = 0;
        long[] sum = new long[str.length() + 1];
        char[] str_arr = str.toCharArray();
        int count = 0;
        //时间：O(n)扫描  空间: O(n)
        //sum[i]表示第(i+1)个1左边的0的个数
        //最后 记录末尾0的个数 数据可能造成空间浪费
        for(int i = 0;i < str.length();i++){
            if(str_arr[i] == '1'){
                count++;
            }else{ //记录第n个1左边0的个数
                sum[count]++;
            }
        }

                //计算res
        if(k == 0){ // 当k==0 直接求连续0的子串之和
            for(int i = 0; i <= count;i++){
                res += sum[i]*(sum[i]+1)/2;
            }
        }else{ // 当k!=0 求左右两边的子串组合（+1是因为空串""）
            for(int i = 0; i + k <= count;i++){
                res += (sum[i]+1) * (sum[i+k] + 1);
            }
        }

        System.out.println(res);

    }
}

上个 的暴力吧：

#include <bits/stdc++.h>
const int maxn = 1e6 + 5;
char s[maxn];
int sum[maxn],k;
int main() {
    scanf("%d%s", &k,s + 1);
    int n = strlen(s + 1);
    for (int i = 1; i <= n; ++i)    sum[i] = sum[i - 1] + (s[i] == '1');
    long long ans = 0;
    for (int j = 1; j <= n; ++j) {
        ans += std::upper_bound(sum, sum + j, sum[j] - k) -
                std::lower_bound(sum, sum + j, sum[j] - k);
    }
    printf("%lld\n", ans);
    return 0;
}

这个明明是个O(n)的尺取，额外空间是O(1)的。

弄个左右指针框住一段恰好k个1的最短的区间，然后左右延伸出去数一数两边的0。

2 4 9 10 14 18

考虑第5个1，位置是14，假如k=3，第2个1的位置是4。
那么包含9，10，11这三个1的所有可能性可以表示为：
右侧滑动范围(14,18]，左侧滑动范围((4,9]，可能性有(18-14)*(9-4)=20种。
然后改变末位1的位置求得总共的可能性。

下附代码：

package main

import "fmt"

func main()  {
    var k,ans int
    var str string
    fmt.Scan(&k,&str)
    pos:= []int{-1}
    for i,v:=range(str){
        if v==49{    //"1"的ASCII码为49
            pos=append(pos, i)
        }
    }
    if k>=len(pos){
        fmt.Println(0)
        return
    }
    pos=append(pos, len(str))
    if k==0{
        for i:=k;i<len(pos)-1;i++{
            ans+=(pos[i+1]-pos[i]-1)*(pos[i+1]-pos[i])/2
        }
    }else {
        for i := k; i < len(pos)-1; i++ {
            ans += (pos[i+1] - pos[i]) * (pos[i-k+1] - pos[i-k])
        }
    }
    fmt.Println(ans)
}

枚举即可，查看题解请移步至 A 或 B 或 C

//引用楼上思路：数出所有‘1’的左右各有多少0，
//然后第n个1的左边的0的个数为a，
//第n + k个1的右边的0的个数为b，
//那么这个组合有（a + 1） * （b + 1）种可能，
//将所有可能加起来就可以了。
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_map>
using namespace std;
int main()
{
    int k; string s;
    while (cin >> k >> s)
    {
        int sum = 0;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == '1')
                sum++;
        }//计算1的个数
        if (sum < k)
        {
            cout << 0 << endl; break;
        }//特殊情况1的个数小于k
        vector<pair<int,int>> zeros(s.size()+1,pair<int,int>(0,0)); 
        long num = 0; long long res = 0;//结果必须用Long long 存储
        int i = 0;
        for (; i < s.size();i++)
        {
            if (s[i] == '1')//计算每个1右侧0的个数
            {
                //顺便计算k=0时的种类数，比如有三个连续0，则种类数位1+2+3=3*（1+3）/2
                zeros[i].first = num; res +=(long long)num * (num + 1) / 2;// cout << num;
                num = 0;
            }
            else
                num++;
        }
        //cout << endl;
        if(s[--i]=='0')//考虑循环中不是1结尾的情况
            res+=(long long)num * (num + 1) / 2;
        if (k == 0)
        {
            cout << res << endl; break;//k=0时特殊处理
        }
        num = 0;
        i = s.size() - 1;
        for (; i >=0; i--)//统计1的左侧0的个数
        {
            if (s[i] == '1')
            {
                zeros[i].second = num; //cout << num;
                num = 0;
            }
            else
                num++;
        }
        //cout << endl;
        res = 0;
        if (k == 1)//如果k等于1，则对于每个1，种类数等于左侧的0的个数+1与右侧0的个数+1的乘积
        {
            for (int i = 0; i < s.size(); i++)
            {
                if(s[i]=='1')
                    res+= (zeros[i].first + 1) * (zeros[i].second + 1);
            }
            cout << res << endl; break;
        }
        int left = 0; //如果k不等于1，则对于每个k个1，种类个数，等于最左侧的1左侧零的个数+1与最右侧1的右侧0的个数+1的乘积
        while (left < s.size() && s[left]!= '1')
            left++;
        int l = 0; int right = 0; bool kk = 0;
        while (right < s.size() && l < k)
        {
            if (s[right] == '1')l++; right++; kk = 1;
        }//此时left和right之间包含k个1，且分别为左右端点
        res = 0; if(kk)right--;
        while (left <= right && right < s.size())
        {
            if (l == k && s[left] == '1')//计算
                res += (zeros[left].first + 1) * (zeros[right].second + 1);
            if (l == k)//左侧移动到下一个1
            { 
                left++;
                while (s[left] != '1')
                    left++;
                l--;
            }
            else
                break;            
            if (l < k)//右侧移动到下一个1
            {
                right++;
                while (right<s.size()&&s[right] != '1')
                    right++;
                l++;
            }
        }
        cout << res << endl;
    }
    return 0;
}

#include<iostream>
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
ll get_res(string &s, int K) {
    ll res = 0;
    ll count = 0;
    vector<int> Index;
    Index.push_back(-1);
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '1') {
            count++;
            Index.push_back(i);
        }
    }
    if (count < K)return res;
    Index.push_back(s.size());
    count = 0;
    int i = 1;
    if (K == 0) {
        if(Index.size()==2)return ll((1+s.size())*s.size()/2);
        while (i  < Index.size()) {
            count += (1+Index[i]-Index[i-1]-1)*(Index[i] - Index[i - 1] - 1)/2;
            i++;
        }
        return count;
    }
    while (i + K - 1 < Index.size()-1) {
        int temp1 = Index[i] - Index[i - 1] - 1;
        count += 1+(Index[i]-Index[i-1]-1 + Index[i + K] - Index[i+K-1] - 1 + (Index[i] - Index[i - 1] - 1) * (Index[i + K] - Index[i+K-1] - 1));
        i++;
    }
    return count;
}
int  main(){
    int K;
    cin>>K;
    string s;
    cin>>s;
    ll res = get_res(s,K);
    cout<<res;
    return 0;
}

我有一个想法：就是数出所有‘1’的左右各有多少0，然后第n个1的左边的0的个数为a，第n+k个1的右边的0的个数为b，那么这个组合有（a+1）*（b+1）种可能，将所有可能加起来就可以了。

比如说

输入

1
1010

输出

6

那么第一个1左边0个0，右边1个0，那么有12=2种符合条件的子串，第二个1左边1个0 ，右边1个0，有22=4种可能，总共2+4=6种可能。

优化前面楼主的代码，子串匹配问题。子串要求有k个1，则创建一个k+1大小的数组，进行子串表示。（低n个字符是否能满足子串，当第n个字符为0时，跟前面k个1有关，当第n个字符为1时，跟前面k-1个1有关）。长度为k+1的数组status存放了相连的k+1个1后面0的个数。如第n个字符为子串的最后一个字符，则该子串必须包含第n字符以及前面相连最近的k个为1的字符，可以在字符的前面加0，每添加一个连续的0，则多一个子串的组合。

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        sc.nextLine();
        String str = sc.nextLine();
        char[] strChar = str.toCharArray();
        int[] status = new int[k + 2];
        status[0] = 1;
        int num = 0;
        long result = 0;
        for (char c : strChar) {
            if (c == '1') num++;
            if (c == '1') status[(num) % (k + 1)] = 0;
            if (num >= k) result+= status[(num - k) % (k + 1)];
            status[num % (k + 1)]++;
        }
        System.out.println(result);
    }
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int k = scan.nextInt();
        String s = scan.next();
        char[] arr = s.toCharArray();
        int count = 0, N = s.length(), map[] = new int[N + 2];
        long result = 0;
        map[0] = -1;
        for(int i = 0; i < N; i++) {
            char c = arr[i];
            // 当 K 为 0 的情况下
            if(c == '0') {
                if(k == 0) {
                    result += (i - map[count]);
                } else if(count >= k) {
                    result += map[count - k + 1] - map[count - k];
                }
            } else {
                map[++count] = i;
                if(count >= k && k != 0) {    // 这里 k!=0 因为当 k 为0, 则所有 1 直接失效了
                    result += map[count - k + 1] - map[count - k];
                }
            }
        }
        System.out.println(result);
    }
}