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

如何统计最多翻转 k 个 0 时获得最长连续 1 子数组的方案数

本文介绍在二进制数组中，通过至多翻转 k 个 0 得到最长连续 1 子数组的所有可能方案数量的高效计算方法，基于滑动窗口思想，时间复杂度 o(n)，空间复杂度 o(1)。

本文介绍在二进制数组中，通过至多翻转 k 个 0 得到最长连续 1 子数组的所有可能方案数量的高效计算方法，基于滑动窗口思想，时间复杂度 o(n)，空间复杂度 o(1)。

要解决“统计最多翻转 k 个 0 后能得到最长连续 1 的方案数”这一问题，核心在于：不仅需找出最大长度 maxLen，还需统计所有长度恰好为 maxLen 且包含 ≤ k 个 0 的滑动窗口个数。这与经典「最长连续 1 的个数 III」（LeetCode 1004）不同——后者只返回最大长度，而本题要求的是达成该最大长度的可行翻转方案数（即满足条件的子数组个数）。

✅ 解题思路：双指针 + 动态计数

我们沿用滑动窗口（双指针）框架，但需额外维护：

maxLen：当前观测到的最长合法窗口长度（即含 ≤ k 个 0 的最长子数组长度）；
count：长度等于 maxLen 的合法窗口数量。

关键观察：

每一个满足 zeros_in_window

算法步骤如下：

初始化左指针 i = 0，计数器 zeros = 0，maxLen = 0，count = 0；
遍历右指针 j 从 0 到 n-1：
- 若 nums[j] == 0，则 zeros++；
- 当 zeros > k 时，收缩左边界：若 nums[i] == 0，则 zeros--，i++；
- 此时窗口 [i, j] 是合法的（含 ≤ k 个 0），计算长度 len = j - i + 1；
- 若 len > maxLen：更新 maxLen = len，重置 count = 1；
- 若 len == maxLen：count++；
最终返回 count。

注意：此处窗口是闭区间，长度为 j−i+1（区别于原题返回 j−i 的开区间写法），更直观对应子数组方案。

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

窗口 [i,j]	子数组	0 的个数	长度	是否更新？	说明
[0,0]	[1]	0	1	maxLen=1, count=1	初始
[0,1]	[1,0]	1	2	maxLen=2, count=1	新最大
[0,2]	[1,0,1]	1	3	maxLen=3, count=1	新最大
[0,3]	[1,0,1,0]	2 > k	—	收缩 → i=1	不合法
[1,3]	[0,1,0]	2 > k	—	收缩 → i=2
[2,4]	[1,0,1]	1	3	count=2	再次出现长度 3
[3,5]	[0,1,0]	2 → 收缩后 [4,5]→[1,0]→继续扩展…
[4,6]	[1,0,1]	1	3	count=3	第三次

最终 count = 3，对应三种翻转方式：翻转索引 1、3 或 5 处的 0，得到 1110101 / 1011101 / 1010111。

? 代码实现（Java）

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

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

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