题解 | 小红的01子序列构造（easy）

双指针类型题目：共同特征，在一端区间内满足条件。这题要求在一段区间内满足k个01子序列，那么直接左右指针先指向起点都是s[0]位置。r指针负责往后扩大范围，再者我们分析何时达到k个01子序列，首先0肯定要在1前面才能满足01的要求，前面有多少个0那么在0之后的1都能和其组合，这样我们就要实时记录0和1的个数分别为cnt_0和cnt_1，也要记录cnt也就是当前区间里01子序列的个数。

如果是01序列个数少于k，我们自增r扩大区间范围：那么分析可知如果新加的数是1，那么只有cnt_1自增的时候会贡献前面cnt_0个0与其组合，那么cnt就要加上cnt_0。否则是0就cnt_0自增。

如果01序列大于k个数，我们移动l缩小区间范围：那么分析可知，每移动一位如果是移除了0，那么后面所有1都要失去一次组合，那么cnt要减去cnt_1，否则是1就只要cnt_1自减。

如果是刚好cnt==k，那么输出l+1和r+1即可直接返回结束。

否则最后输出-1即可，注意l和r都要在n的范围内。

#include<bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    if (s.length() == 1) {
        cout << "-1" << endl;
        return;
    }
    int l = 0;
    int r = 0;
    int cnt=0;//记录有当前有几组01字序列
    int cnt_1=0;
    int cnt_0=0;
    if(s[0]=='0'){
        cnt_0++;
    }else cnt_1++;
    while(l<n&&r<n){
        if(cnt==k){
            cout<<l+1<<" "<<r+1<<endl;
            return;
        }else if(cnt<k){//说明r指针还需要继续往后加
            r++;
            if(s[r]=='1'){
                cnt_1++;
                cnt+=cnt_0;
            }else{
                cnt_0++;
            }   
        }else{//说明已经超过了k的限制，需要移动l指针
            if(s[l]=='0'){
                cnt_0--;
                cnt-=cnt_1;
            }else{
                cnt_1--;
            }
            l++;
        }
    }
    cout<<"-1"<<endl;//之前没有输出结果这里输出代表寻找失败
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}