双指针解法

若区间内总数少于要求个数则右界右移 若区间内总数多于要求个数则左界右移

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(0);cin.tie(0);
    ll n,k,i,cn0,cn1;
    cin>>n>>k;//长度和要求个数
    char c;string s;cin>>s;
    if (s[0]=='0'){cn0=1;cn1=0;}else{cn0=0;cn1=1;} //初始化
    ll a0=0,a1=0,a2=0;//双指针解法  左界,右界,总数
    while(a0<n&&a1<n){
        if(a2==k){
            cout<<a0+1<<' '<<a1+1<<endl;
            return 0;
        }else if(a2<k){//右向右
            a1++;
            if(s[a1]=='0')cn0++;
            else{
                a2+=cn0;
                cn1++;
            }
        }else{//左向右
            if(s[a0]=='0'){
                a2-=cn1;
                cn0--;
            }else cn1--;
            a0++;
        }
    }
    cout<<-1;
    return 0;
}

前缀和+二分解法

前缀和存取01数

二分查找要求区间

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(0);cin.tie(0);
    ll n,k,i;cin>>n>>k;//长度和要求个数
    ll cn0[n+10],cn1[n+10],tt[n+10],ans=-1;
    string s;cin>>s;
    //前缀和
    for (i=1;i<=n;i++) {
        cn0[i]=cn0[i-1];cn1[i]=cn1[i-1];tt[i]=tt[i-1];
        if (s[i-1]=='0')cn0[i]++;
        else{
            cn1[i]++;
            tt[i]+=cn0[i-1];
        }
    }
    //二分
    for(i=1;i<=n;i++){
        ll l=i,r=n,mid;
        while(l<=r){
            mid=(l+r)/2;
            if((tt[mid]-tt[i-1]-1LL*cn0[i-1]*(cn1[mid]-cn1[i-1]))>=k){
                ans=mid;r=mid-1;
            }else l=mid+1;
        }
        if(ans==-1) break;
        if((tt[ans]-tt[i-1]-1LL*cn0[i-1]*(cn1[ans]-cn1[i-1]))==k){
            cout<<i<<" "<<ans; return 0;
        }
    }
    cout<<ans; return 0;
}