本文涉及的基础知识点

C++算法：滑动窗口及双指针总结

LeetCode1004. 最大连续1的个数 III

示例 1：
输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：
输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。
提示：
1 <= nums.length <= 10⁵
nums[i] 不是 0 就是 1
0 <= k <= nums.length

滑动窗口

n = nums.size()
左闭右开空间nums[i…j)表示滑动窗口，其含义为：操作后全部为1。
则只会有这两种情况：
一，j等于n。
二，左闭右闭空间nums[i…j]包括k+1个0，且j最小。
令i1<i2,i1,i2是滑动窗口的左端点，对应的右端点为j1,j2。
则 j1 <= j2。下面分情况证明：
一，j1等于n，则j2等于n。
二，nums[i1…j1]少于k+1个0 $\to$ nums[i2…j1] 小于k+1个0。
时间复杂度：O(n)

代码

核心代码

class Solution {
		public:
			int longestOnes(vector<int>& nums, int k) {
				int ret = 0, cnt0 = 0;
				for (int i = 0, j = 0; i < nums.size(); i++) {
					while (j < nums.size() ) {
						if ((cnt0 == k) && (0 == nums[j])) { break; }
						cnt0 += (0 == nums[j]);
						j++;						
					}
					ret = max(ret, j - i);
					cnt0 -= (nums[i] == 0);
				}
				return ret;
			}
		};

单元测试

vector<int> nums;
		int k;
		TEST_METHOD(TestMethod11)
		{
			nums = { 1,1,1,0,0,0,1,1,1,1,0 }, k = 2;
			auto res = Solution().longestOnes(nums, k);
			AssertEx(6, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1 }, k = 3;
			auto res = Solution().longestOnes(nums, k);
			AssertEx(10, res);
		}