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

题目链接

题目描述

给定一个仅由字符 '0' 和 '1' 组成的字符串 $s$ ，长度为 $n$ 。小红想找到一个闭区间 $[l, r]$ ，使得在子串 $s[l \dots r]$ 中，恰好存在 $k$ 个严格等于 "01" 的子序列。

请你输出任意一个满足条件的区间；若不存在，则输出 -1。

解题思路

这个问题可以高效地使用**滑动窗口（双指针）**方法来解决。

首先，我们需要明确如何计算一个字符串中 "01" 子序列的数量。对于字符串中的每一个字符 '1'，它能与它左边的任意一个 '0' 组成一个 "01" 子序列。因此，一个 '1' 对 "01" 子序列总数的贡献就等于它左边 '0' 的数量。整个字符串中 "01" 子序列的总数就是所有 '1' 的贡献之和。

基于这个思想，我们可以使用两个指针， $left$ 和 $right$ ，来维护一个动态的窗口 $[left, right]$ 。我们还需要一些变量来维护窗口内的状态：

$zeros\_count$ ：记录当前窗口内 '0' 的数量。
$ones\_count$ ：记录当前窗口内 '1' 的数量。
$current\_k$ ：记录当前窗口内 "01" 子序列的总数。

算法流程如下：

初始化 $left = 0$ ，以及三个计数器为 0。
让右指针 $right$ 从 $0$ 遍历到 $n-1$ ，不断扩大窗口：
- 读入新字符 $s[right]$ 。
- 如果 $s[right]$ 是 '0'，则 $zeros\_count$ 增加 1。
- 如果 $s[right]$ 是 '1'，它将与窗口内已有的 $zeros\_count$ 个 '0' 形成新的 "01" 子序列，所以 $current\_k$ 增加 $zeros\_count$ ， $ones\_count$ 增加 1。
在每一步扩大窗口后，检查 $current\_k$ 是否大于 $k$ 。如果是，说明当前窗口内的 "01" 子序列太多，需要从左边收缩窗口：
- 当 $current\_k > k$ 时，持续移动左指针 $left$ ：
  - 如果要移除的字符 $s[left]$ 是 '0'，那么窗口内所有的 '1' 都失去了一个可以配对的 '0'。因此， $current\_k$ 需要减去当前窗口内的 $ones\_count$ 。同时， $zeros\_count$ 减 1。
  - 如果要移除的字符 $s[left]$ 是 '1'，移除它不会影响其他 "01" 子序列的构成（因为它在最左边，没有 '0' 在它前面），所以 $current\_k$ 不变。我们只需将 $ones\_count$ 减 1。
- 收缩窗口的循环结束后， $current\_k$ 将小于或等于 $k$ 。
在每次外层循环（移动 $right$ ）的末尾，检查 $current\_k$ 是否恰好等于 $k$ 。如果是，我们就找到了一个满足条件的区间 $[left, right]$ ，可以立即输出并终止程序。
如果整个过程结束后都没有找到满足条件的区间，则输出 -1。

这个算法中，左右指针都只向右移动，最多遍历一次字符串，因此总的时间复杂度为 $O(N)$ 。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    long long k;
    cin >> n >> k;
    string s;
    cin >> s;

    long long current_k = 0;
    long long zeros_count = 0;
    long long ones_count = 0;
    int left = 0;

    for (int right = 0; right < n; ++right) {
        if (s[right] == '0') {
            zeros_count++;
        } else { // s[right] == '1'
            ones_count++;
            current_k += zeros_count;
        }

        while (current_k > k && left <= right) {
            if (s[left] == '0') {
                current_k -= ones_count;
                zeros_count--;
            } else { // s[left] == '1'
                ones_count--;
            }
            left++;
        }
        
        if (current_k == k) {
            cout << left + 1 << " " << right + 1 << endl;
            return 0;
        }
    }

    cout << -1 << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        String s = sc.next();

        long currentK = 0;
        long zerosCount = 0;
        long onesCount = 0;
        int left = 0;

        for (int right = 0; right < n; right++) {
            char c = s.charAt(right);
            if (c == '0') {
                zerosCount++;
            } else { // c == '1'
                onesCount++;
                currentK += zerosCount;
            }

            while (currentK > k && left <= right) {
                char leftChar = s.charAt(left);
                if (leftChar == '0') {
                    currentK -= onesCount;
                    zerosCount--;
                } else { // leftChar == '1'
                    onesCount--;
                }
                left++;
            }

            if (currentK == k) {
                System.out.println((left + 1) + " " + (right + 1));
                return;
            }
        }

        System.out.println(-1);
    }
}

def main():
    n, k = map(int, input().split())
    s = input().strip()

    current_k = 0
    zeros_count = 0
    ones_count = 0
    left = 0

    for right in range(n):
        if s[right] == '0':
            zeros_count += 1
        else: # s[right] == '1'
            ones_count += 1
            current_k += zeros_count

        while current_k > k and left <= right:
            if s[left] == '0':
                current_k -= ones_count
                zeros_count -= 1
            else: # s[left] == '1'
                ones_count -= 1
            left += 1

        if current_k == k:
            print(left + 1, right + 1)
            return

    print(-1)

if __name__ == "__main__":
    main()

算法及复杂度

算法：滑动窗口（双指针）。
时间复杂度： $O(N)$ ，其中 $N$ 是字符串 $s$ 的长度。左右指针 $left$ 和 $right$ 都最多遍历一次字符串。
空间复杂度： $O(N)$ ，用于存储输入的字符串 $s$ 。