最长1序列翻转k个0的方案数统计

本文深入探讨了在二进制数组中，最多翻转k个0为1的前提下，不仅高效求出最长连续1子数组的长度（O(n)时间、O(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 <= k，它就对应一种合法翻转方案（将其中所有 0 翻为 1 后，该区间全为 1）；
• 我们关注的是：这些合法窗口中，长度等于全局最大连续 1 长度 maxLen 的窗口有多少个 —— 每个这样的窗口唯一对应一种翻转方式（翻转其内部所有 0）。

✅ 算法步骤（一次遍历）

1. 初始化 left = 0, zeroCount = 0, maxLen = 0, ways = 0；
2. 遍历 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，忽略）

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

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

最终 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 < n; right++) {
        if (nums[right] == 0) zeroCount++;

        while (zeroCount > 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;
}

⚠️ 注意事项

• 本解法统计的是不同起止位置的合法窗口数量，而非翻转集合的组合数（后者可能指数级爆炸，不符合题意）；
• 当 k = 0 时，等价于统计原数组中最长连续 1 的出现次数；
• 时间复杂度严格 O(n)：每个元素最多进出窗口一次；
• 空间复杂度 O(1)，仅使用常量额外变量；
• 数组为 int[] 且保证二进制值（0/1），无需额外校验。

通过将经典滑动窗口从“求极值”升级为“计数极值方案”，我们以最小开销解锁了更丰富的分析能力 —— 这正是算法设计中“一题多解、一解多用”的典型体现。

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持golang学习网！更多关于文章的相关知识，也可关注golang学习网公众号。