Java题解 | 滑动窗口解决

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long k = in.nextLong();
        in.nextLine();
        String s = in.nextLine();
        char[] c = s.toCharArray();
        int l = 0, r = 0, x = 0, y = 0;
        long cnt = 0;
        while (r < n) {
            if (c[r++] == '0') x++;
            else {
                y++;
                cnt += x;
            }
            while (cnt > k) {
                if (c[l++] == '0') {
                    x--;
                    cnt -= y;
                }else y--;
            }
            if (cnt == k) break;
        }
        if (cnt == k) System.out.printf("%d %d", l + 1, r);
        else System.out.print(-1);
        in.close();
    }
}

维护窗口内0的数量和1的数量，以及01对数量，计为x、y和cnt。

当cnt小于k时窗口向右扩张，遇到1时cnt+=x；遇到0时y++。

当cnt大于k时窗口左端点右移，如果去掉的是0，cnt-=y，x--；去掉的是1，y--。

cnt等于k时break