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

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        sc.nextLine();
        String s = sc.nextLine();
        //每个1前面有几个0,就能个这个1组成多少对01子序列
        //使用l和r两个位置，先将r一直向右移动，一旦[l,r]中01序列数量超过了k，就将l右移。
        int l = 0, r = 0;
        int cnt0 = 0, cnt1 = 0; //分别记录区间[l,r]中0和1的个数
        //TODO 为了下方先进行r++,这里先处理0这个位置
        if (s.charAt(0) == '0')cnt0++;
        if (s.charAt(0) == '1')cnt1++;
        long cnt = 0; //记录区间[l,r]中01子序列的个数
        while (l < n && r < n) {
            if (cnt == k) {
                System.out.println((l + 1) + " " + (r + 1));
                return;
            }
            if (cnt < k) { //如果子序列个数小于k,需要右端点右移
                //TODO 这里右端点一定要先考虑右移
                r++;//右端点右移
                if (r >= n) { // 添加越界判断
                    break;
                }
                //若右端点是1,加进来后,前面所有的0都可以和这个1组成01子序列,所有总个数+cnt0
                if (s.charAt(r) == '1') {
                    cnt1++;
                    cnt += cnt0;
                } else { //如果右端点是0,加进来后，对答案毫无影响，只要cnt0加1
                    cnt0++;
                }
                //TODO 如果右端点在这里右移,会导致可能cnt+=cnt0后已经大于k了,但是这里还是r++
            } else { //如果子序列个数大于k,需要左端点右移
                //若左端点是1,排出序列后，对答案毫无影响,但是cnt1需要减1
                if (s.charAt(l) == '1') {
                    cnt1--;
                } else { //若左端点是0,排出去后,后面的所有1的结果都减少了1个,所有01子序列总个数-cnt1
                    cnt0--;
                    cnt -= cnt1;
                }
                //TODO 这里要后进行l++,如果一开始就l++,讨论的就不是真正的左端点了
                l++;//左端点右移
            }
        }
        //如果没有找到01子序列个数等于k的情况,输出-1
        System.out.println(-1);
    }
}