最长连续1子数组解法详解(力扣1004)

问题解析题目要求给定一个二进制数组nums和一个整数k你可以将最多k个0翻转为1。请返回在执行任意次数的翻转操作后数组中最长的连续1子数组的长度 。核心思路将问题转化为寻找一个最长的子数组使得该子数组内0的个数不超过k个。这可以通过滑动窗口同向双指针算法高效解决。算法流程1.初始化左指针left 0窗口内0的计数器zeroCount 0以及结果maxLen 0。2. 右指针right从0开始遍历数组*进窗口如果nums[right] 0则zeroCount。*判断与收缩当zeroCount k时说明当前窗口内0的数量超过了可翻转的上限。此时需要收缩左边界即left右移。如果移出窗口的元素是0则zeroCount--。*更新结果在每次右指针移动并完成可能的窗口收缩后当前窗口[left, right]一定满足条件0的数量 ≤k。此时更新最大长度maxLen max(maxLen, right - left 1)。复杂度分析时间复杂度O(n)每个元素最多被访问两次右指针一次左指针一次。空间复杂度O(1)仅使用了常数个额外变量。C 代码实现class Solution { public: int longestOnes(vectorint nums, int k) { int left 0; // 窗口左边界 int zeroCount 0; // 窗口内0的个数 int maxLen 0; // 记录最大长度 // 右指针遍历整个数组 for (int right 0; right nums.size(); right) { // 1. 右指针元素进窗口 if (nums[right] 0) { zeroCount; } // 2. 判断如果窗口内0的数量超过k需要收缩左边界 while (zeroCount k) { if (nums[left] 0) { zeroCount--; } left; // 左指针右移窗口收缩 } // 3. 更新最大长度 (此时窗口[left, right]一定满足条件) maxLen max(maxLen, right - left 1); } return maxLen; } };参考来源★ 算法OJ题 ★ 力扣1004 - 最大连续 1 的个数 IIIleetcode--1004 最大连续1的个数 III[滑动窗口c]【LeetCode】1004. Max Consecutive Ones III滑动窗口【C算法题】滑动窗口*8Leetcode每日刷题之1004.最大连续1的个数|||(C)