最多允许K次交换的最长子数组 题目描述 给定一个二进制数组 nums （只包含 0 和 1）和一个整数 k ，你最多可以交换 k 次任意两个位置（交换不要求相邻）的 0 和 1。目标是使得交换后数组中最长的连续 1 的子数组长度最大，并返回这个最大长度。 注意 ：交换操作只是题目中允许的手段，最终我们关心的是 连续 1 的子数组长度 ，且交换次数限制在 k 次内。 示例 输入：nums = [ 1,1,0,0,1,1,1,0,1,0 ], k = 2 输出：7 解释：交换位置 3 的 0 和位置 8 的 1（从 0 开始索引），得到 [ 1,1,1,0,1,1,1,0,0,0 ]，连续 1 的最长子数组长度为 7。 解题过程 1. 问题转化 本题等价于：在数组中找到一个子数组，使得这个子数组中的 0 的个数不超过 k （因为每个 0 可以通过一次交换变成 1，但需消耗一次交换机会）。我们要找的就是这样一个子数组，它的长度最大。 为什么？因为在子数组内，我们可以将里面的 0 交换成 1（用子数组外的 1 交换进来），只要交换次数 ≤ k 即可。注意题目允许交换任意两个位置的 0 和 1，所以只要子数组内 0 的个数 ≤ k，我们总能用子数组外的 1 换掉这些 0，从而让子数组全为 1。 2. 确定方法 这可以转化为一个 滑动窗口 问题（本质是双指针），属于线性动态规划的思想（不过这里是同向双指针，维护一个满足条件的窗口）。 用两个指针 left 和 right 表示窗口的左右边界。 记录窗口内 0 的个数 zeroCount 。 当 zeroCount > k 时，移动 left 指针，直到 zeroCount ≤ k 。 在每一步，窗口长度 right - left + 1 是当前满足条件的子数组长度，用其更新最大长度。 3. 算法步骤 初始化 left = 0 , zeroCount = 0 , maxLen = 0 。 遍历 right 从 0 到 n-1： a. 如果 nums[right] == 0 ，则 zeroCount++ 。 b. 当 zeroCount > k 时： 如果 nums[left] == 0 ，则 zeroCount-- 。 left++ 。 c. 此时窗口内 0 的个数 ≤ k，更新 maxLen = max(maxLen, right - left + 1) 。 返回 maxLen 。 4. 模拟示例 nums = [ 1,1,0,0,1,1,1,0,1,0 ], k=2 right=0: 窗口[ 1 ], zero=0, len=1, max=1 right=1: 窗口[ 1,1 ], zero=0, len=2, max=2 right=2: 窗口[ 1,1,0 ], zero=1, len=3, max=3 right=3: 窗口[ 1,1,0,0 ], zero=2, len=4, max=4 right=4: 窗口[ 1,1,0,0,1 ], zero=2, len=5, max=5 right=5: 窗口[ 1,1,0,0,1,1 ], zero=2, len=6, max=6 right=6: 窗口[ 1,1,0,0,1,1,1 ], zero=2, len=7, max=7 right=7: 加入0 → zero=3>k，移动 left 直到 zero≤2： left 从0移到1，zero仍3（因为 left 原来指向1，不是0） left=1, 检查nums[ 1]=1，继续 left=2，nums[ 2]=0，zero=2，停止。窗口变为 [ 0,0,1,1,1,0 ]（索引2到7） 长度=6，max仍=7 right=8: 加入1 → zero=2，窗口长=7，max=7 right=9: 加入0 → zero=3>k，移动 left 直到 zero≤2： left=2时去掉nums[ 2]=0，zero=2，窗口变为 [ 0,1,1,1,0,1,0 ]（索引3到9），长度=7，max=7 最终 max=7。 5. 时间复杂度 O(n)，每个元素至多被 left 和 right 访问一次。 空间复杂度 O(1)。 6. 扩展思考 如果题目改为最多可以交换 k 次 任意两个元素 （不一定是 0 和 1 交换，可以是 1 和 1 交换），结果是否一样？ —— 一样，因为交换 1 和 1 不会改变 0 的个数，所以限制仍然是子数组内 0 的个数 ≤ k。