求最多翻转k个0后获得最长连续1的可行方案数

这是LeetCode题目《最大连续1的个数 III》的变种问题。给定二进制数组nums和整数k，已知通过翻转最多k个0可以得到数组中最长的连续1序列，现需计算能得到该最长连续1序列的可行方案数量。

示例 #

• 输入数组：[1,0,1,0,1,0,1]
• K = 1
• 可行方案对应的翻转结果：
  • 翻转索引1的0 → [1,1,1,0,1,0,1]（最长连续1为前3个元素）
  • 翻转索引3的0 → [1,0,1,1,1,0,1]（最长连续1为中间3个元素）
  • 翻转索引5的0 → [1,0,1,0,1,1,1]（最长连续1为后3个元素）
• 可行方案总数：3

约束条件 #

• 输入数组长度范围：1 ≤ len(nums) ≤ 10^5
• k的取值范围：0 ≤ k ≤ len(nums)

原问题（最长连续1长度）的实现代码 #

public int longestOnes(int[] A, int K) {
    int i = 0, j;
    for (j = 0; j < A.length; ++j) {
        if (A[j] == 0) K--;
        if (K < 0 && A[i++] == 0) K++;
    }
    return j - i;
}

变种问题解决方案 #

思路 #

1. 计算最长连续1长度：先用原问题的滑动窗口代码得到最长连续1序列的长度max_len。
2. 统计符合条件的窗口数量：再次使用滑动窗口，遍历所有长度为max_len的子数组，统计其中0的数量≤k的子数组个数——每个这样的子数组对应一种可行方案（翻转该子数组内的所有0，即可得到长度为max_len的连续1序列）。

实现代码 #

public int countLongestOnes(int[] nums, int k) {
    int maxLen = longestOnes(nums, k);
    int n = nums.length;
    if (maxLen == 0) return 0;
    
    // 统计第一个窗口内的0的数量
    int count0 = 0;
    for (int i = 0; i < maxLen; i++) {
        if (nums[i] == 0) count0++;
    }
    
    int res = count0 <= k ? 1 : 0;
    // 滑动窗口遍历剩余窗口
    for (int right = maxLen; right < n; right++) {
        int left = right - maxLen;
        if (nums[right] == 0) count0++;
        if (nums[left] == 0) count0--;
        if (count0 <= k) res++;
    }
    return res;
}

// 原问题的最长连续1长度计算函数
private int longestOnes(int[] A, int K) {
    int i = 0, j;
    for (j = 0; j < A.length; ++j) {
        if (A[j] == 0) K--;
        if (K < 0 && A[i++] == 0) K++;
    }
    return j - i;
}

复杂度分析 #

• 时间复杂度：O(n)，两次线性遍历数组，整体为线性时间复杂度。
• 空间复杂度：O(1)，仅使用常数级额外空间。

内容的提问来源于stack exchange，提问作者Learner