如何统计最多翻转 k 个 0 时达到最长连续 1 的方案数-java教程-PHP中文网

如何统计最多翻转 k 个 0 时达到最长连续 1 的方案数

本文介绍在二进制数组中，允许最多将 k 个 0 翻转为 1 的前提下，求解「最长连续 1 子数组长度」的同时，统计所有能达成该最大长度的不同翻转方案数量的高效算法，时间复杂度 O(n)，空间复杂度 O(1)。

本文介绍在二进制数组中，允许最多将 k 个 0 翻转为 1 的前提下，求解「最长连续 1 子数组长度」的同时，**统计所有能达成该最大长度的不同翻转方案数量**的高效算法，时间复杂度 o(n)，空间复杂度 o(1)。

要解决“方案数”问题，不能仅复用标准滑动窗口求最大长度的代码（如 longestOnes），而需在窗口滑动过程中主动记录所有恰好构成当前全局最大长度的有效窗口。

核心思想是：

使用双指针 left 和 right 维护一个滑动窗口；
窗口内至多包含 k 个 0（即允许翻转的额度未超支）；
每当窗口满足 zeros_in_window
我们关注的是：这些合法窗口中，长度等于全局最大连续 1 长度 maxLen 的窗口有多少个 —— 每个这样的窗口唯一对应一种翻转方式（翻转其内部所有 0）。

✅ 算法步骤（一次遍历）

初始化 left = 0, zeroCount = 0, maxLen = 0, ways = 0；
遍历 right 从 0 到 n-1：
- 若 nums[right] == 0，zeroCount++；
- 收缩窗口：当 zeroCount > k 时，若 nums[left] == 0，则 zeroCount--，left++；
- 此时 [left, right] 是一个有效窗口（zeroCount ≤ k），计算长度 len = right - left + 1；
- 若 len > maxLen：更新 maxLen = len，重置 ways = 1；
- 若 len == maxLen：ways++；
- （若 len

注意：此逻辑确保每个达成 maxLen 的合法窗口都被精确计数一次，且窗口位置不同即视为不同方案（即使翻转的 0 集合有重叠，只要起止索引不同，就代表不同的连续段，对应不同“方式”）。

? 示例演示（nums = [1,0,1,0,1,0,1], k = 1）

right	window (indices)	content	zeros	len	action	maxLen	ways
0	[0,0]	[1]	0	1	new max	1	1
1	[0,1]	[1,0]	1	2	new max	2	1
2	[0,2]	[1,0,1]	1	3	new max	3	1
3	[1,3] → [2,3]	[0,1]→[1,0]	1→1	2	skip (len	3	1
4	[2,4]	[1,0,1]	1	3	match max → ways++	3	2
5	[3,5] → [4,5]	[0,1]→[1,0]	1→1	2	skip	3	2
6	[4,6]	[1,0,1]	1	3	match max → ways++	3	3

最终 ways = 3，对应三种方案：翻转索引 1、3 或 5 处的 0，得到连续 111。

? 关键代码实现

public int countMaxConsecutiveOnesWays(int[] nums, int k) {
    int n = nums.length;
    int left = 0, zeroCount = 0, maxLen = 0, ways = 0;

    for (int right = 0; right  k) {
            if (nums[left] == 0) zeroCount--;
            left++;
        }

        int len = right - left + 1;
        if (len > maxLen) {
            maxLen = len;
            ways = 1;
        } else if (len == maxLen) {
            ways++;
        }
    }
    return ways;
}