统计最多翻转 k 个 0 时获得最长连续 1 子数组的方案数-java教程-PHP中文网

本文介绍如何在 o(n) 时间内，不仅求出二进制数组中最多翻转 k 个 0 后所能得到的最长连续 1 的长度，还准确统计所有能达到该最大长度的不同翻转方案数量。

本文介绍如何在 o(n) 时间内，不仅求出二进制数组中最多翻转 k 个 0 后所能得到的最长连续 1 的长度，还准确统计所有能达到该最大长度的不同翻转方案数量。

解决该问题的核心思想是滑动窗口（双指针）的扩展应用：在经典「最长含至多 k 个 0 的子数组」问题基础上，不只记录最大窗口长度，还需在遍历过程中动态统计有多少个合法窗口恰好达到当前全局最大长度。

? 关键洞察

每一个满足「窗口内 0 的个数 ≤ k」的子数组 [i, j)，对应一种将其中全部 0 翻转为 1 后得到连续 1 的方案；
其翻转后产生的连续 1 长度即为窗口长度 j − i；
我们的目标是：找出所有满足 j − i == maxLen 的合法窗口数量，其中 maxLen 是全局最长可能长度。

✅ 算法步骤（单次遍历）

初始化左指针 i = 0，零计数器 zeros = 0，maxLen = 0，ways = 0；
右指针 j 从 0 到 n−1 遍历：
- 若 nums[j] == 0，则 zeros++；
- 当 zeros > k 时，收缩左边界：若 nums[i] == 0，则 zeros--，i++；
- 此时 [i, j] 是以 j 结尾的最长合法窗口 → 长度 len = j − i + 1；
- 若 len > maxLen：更新 maxLen = len，重置 ways = 1；
- 若 len == maxLen：ways++；
返回 ways。

⚠️ 注意：此处窗口定义为闭区间 [i, j]（即包含两端），与部分实现中使用的半开区间 [i, j) 一致，仅需统一索引逻辑即可。

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

合法窗口中长度为 3 的有三个：

[0,2] → 101 → 翻转索引 1 的 0 → 111
[2,4] → 101 → 翻转索引 3 → 111
[4,6] → 101 → 翻转索引 5 → 111
对应代码中三次触发 len == maxLen == 3，故 ways = 3。

? 参考实现（Java）

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

    for (int j = 0; j  k) {
            if (nums[i] == 0) zeros--;
            i++;
        }

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

? 注意事项

时间复杂度：O(n)，每个元素最多被左右指针各访问一次；
空间复杂度：O(1)，仅使用常量额外空间；
边界处理：当 k == 0 时，等价于统计原数组中最长连续 1 子数组的出现次数；当 k ≥ countOfZeros 时，整个数组可全变为 1，唯一方案（ways = 1）；
方案去重：本解法统计的是不同起止位置的窗口数量，每个窗口对应唯一一组待翻转的 0 的下标集合，因此天然无重复。