本文介绍在二进制数组中，通过至多翻转 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 < n; j++) {
if (nums[j] == 0) zeros++;
// 收缩窗口直至合法
while (zeros > 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;
}⚠️ 注意事项
- 窗口定义一致性：务必使用闭区间 [i, j] 计算长度（+1），避免与原题返回值混淆；
- 边界情况：当 k == 0 时，等价于求原数组中最长连续 1 的个数及其出现次数；当 k ≥ n，答案恒为 1（整个数组可全变 1，仅一种方案）；
- 方案去重：每个窗口 [i, j] 对应唯一翻转集合（即翻转其中所有 0），不同窗口即使结果相同（如 111 出现在不同位置）也视为不同方案，符合题意；
- 复杂度：每个元素最多被访问两次（i 和 j 各一次），严格 O(n) 时间；仅用常量额外空间。
该方法将经典滑动窗口从“求极值”拓展为“计数极值方案”，兼具理论清晰性与工程实用性，适用于各类基于约束子数组枚举的变体问题。
