1004. 最大连续1的个数 III {#1004-最大连续1的个数-III}

解题思路

重点： 题意转换。把「最多可以把 K 个 0 变成 1，求仅包含 1 的最长子数组的长度」转换为 「找出一个最长的子数组，该子数组内最多允许有 K 个 0 」。

经过上面的题意转换，我们可知本题是求最大连续子区间，可以使用滑动窗口方法。滑动窗口的限制条件是：窗口内最多有 K 个 0。

代码思路：

1.使用 l 和 r 两个指针，分别指向滑动窗口的左右边界。

2.r 主动右移： r 指针每次移动一步。当nums[r]为 0，说明滑动窗口内增加了一个 0；

3.l 被动右移： 判断此时窗口内 0 的个数，如果超过了 k，则 l 指针被迫右移，直至窗口内的 0 的个数小于等于 k 为止。

4.滑动窗口长度最大值就是所求。

示例：

以 A= [1,1,1,0,0,0,1,1,1,1,0], K = 2 为例，下面的动图演示了滑动窗口的两个指针的移动情况。

见 1004. 最大连续1的个数 III - 负雪明烛 的题解

|------------------------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | public int longestOnes(int[] nums, int k) { int zero = 0; // 窗口中0的个数 int n = nums.length; int res = 0; for (int r = 0, l = 0; r < n; r++) { if (nums[r] == 0) zero++; // r主动右移形成新的窗口 // 窗口内的0个数>k代表不符合题意->此时l应被动移动至符合对应r要求的位置 while (zero > k) { if (nums[l] == 0) zero--; l++; } // 维护每一轮r对应的窗口长度最大值就是res res = Math.max(res, r - l + 1); } return res; } |

分享滑动窗口模板

《挑战程序设计竞赛》这本书中把滑动窗口叫做「虫取法」，我觉得非常生动形象。因为滑动窗口的两个指针移动的过程和虫子爬动的过程非常像：前脚不动，把后脚移动过来；后脚不动，把前脚向前移动。

我分享一个滑动窗口的模板，能解决大多数的滑动窗口问题：

|---------------------------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | public int[] findSubArray(int[] nums){ int n = num.length; // 数组or字符串长度 int l = 0, r = 0; // 双指针，表示当前遍历的区间[l, r]，闭区间 int sum = 0 // 用于统计 子数组or子区间 是否有效，根据题目可能会改成求和or计数 int res = 0 // 保存最大的满足题目要求的 子数组or子串 长度 while (r < n){ // 当右边的指针没有搜索到 数组or字符串 的结尾 sum += nums[r] // 增加当前右边指针的数字or字符的求和or计数 while 区间[l, r]不符合题意{ sum -= nums[l] // 移动左指针前需要从sum中减少l位置字符的求和or计数 l++ // 真正的移动左指针，注意不能跟上面一行代码写反 } // 此时需要一直移动左指针，直至找到一个符合题意的区间 // 到 while 结束时，我们找到了一个符合题意要求的 子数组or子串 res = Math.max(res, r - l + 1) // 需要更新结果 r++ // 移动右指针，去探索新的区间 } return res } |

滑动窗口中用到了左右两个指针，它们移动的思路是：以右指针作为驱动，拖着左指针向前走。右指针每次只移动一步，而左指针在内部 while 循环中每次可能移动多步。右指针是主动前移，探索未知的新区域；左指针是被迫移动，负责寻找满足题意的区间。

模板的整体思想是：

1.定义两个指针 l 和 r 分别指向区间的开头和结尾，注意是闭区间；定义 sum 用来统计该区间内的各个字符出现次数；

2.第一重 while 循环是为了判断 r 指针的位置是否超出了数组边界；当 r 每次到了新位置，需要增加 r 指针的求和/计数；

3.第二重 while 循环是让 l 指针向右移动到 [l, r] 区间符合题意的位置；当 l 每次移动到了新位置，需要减少 l 指针的求和/计数；

4.在第二重 while 循环之后，成功找到了一个符合题意的 [l, r] 区间，题目要求最大的区间长度，因此更新 res = max(res, 当前区间的长度) 。

5.r 指针每次向右移动一步，开始探索新的区间。

6.模板中的 sum 需要根据题目意思具体去修改，本题是求和题目因此把sum 定义成整数用于求和；如果是计数题目，就需要改成字典用于计数。当左右指针发生变化的时候，都需要更新 sum 。

7.另外一个需要根据题目去修改的是内层 while 循环的判断条件，即： 区间 [l, r] 不符合题意 。对于本题而言，就是该区间内的 0 的个数 超过了 2 。

滑窗题目主要有两种类型：

1.窗口大小固定，例如为10，这时候相当于左右边界必定严格同步移动。

2.左指针l不回退类型，这类型一般是新加入nums[r]使得回退必定不符合条件，旧的nums[r]已经不符合条件，这种也可以利用滑窗的思想求解。

再来一道练习题：

LC209. 长度最小的子数组 {#LC209-长度最小的子数组}

给定一个含有n个正整数的数组和一个正整数target 。
找出该数组中满足其和≥ target 的长度最小的连续子数组〔numsl，numsl+1，...，numsr-1,numsr]，并返回其长度。如果不存在符合条件的子数组，返回0。
示例1:
输入： target = 7, nums = [2,3,1,2,4,3] 输出：2
解释：子数组[4,3]是该条件下的长度最小的了教组。
示例2:
输入： target = 4，nums = [1,4,4] 输出：1
示例3:
输入： target = 11，nums = [1,1,1,1,1,1,1,1] 输出：0

思路：

滑动窗口:

这一题最关键的字眼"≥ target 的长度最小的 连续子数组"

这个字眼可以联想到很多东西

1.连续 子数组：是连续的，因此可以与前缀和进行结合（实际上sum变量是一种对于前缀和的优化写法，目的是快速计算窗口的和）

同时，连续子数组，左右指针 为边界就可以确定一个连续子数组->滑动窗口

因此这一题的的提示已经非常明确了，必定是用滑窗

2.长度最小：一般来说求最小长度这种全局最优状态，可以考虑动态规划 或者一路维护

这里用dp的话，状态就是nums[i]结尾的最大长度，显然不太合适，dp[i-1]与dp[i]没有很明显的联系

那么就需要一路维护，求出以nums[r]为右边界的窗口的最小长度，r∈[0,len-1]

维护好nums[0]~nums[len-1]为右边界的合法窗口长度，就是全局的合法窗口最小值，也就是所求！！！

|---------------------------------------------------------------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | class Solution { public int minSubArrayLen(int target, int[] nums) { // 滑窗:右指针主动右移,左指针被动右移 int res = Integer.MAX_VALUE; int len = nums.length; int l = 0, r = 0; // 维护当前窗口[l,r]的总和 int sum = 0; // 主动移动右指针 for (; r < len; r++) { // 计算当前窗口[l,r]的和:新加入的元素只有nums[r] // r指针可能要循环多次才能找到符合条件的[l,r],因为l右移至不符合sum>=target sum += nums[r]; // 若窗口[l,r]满足条件,统计长度并尝试将其尽可能缩小,直至不符合题意 while (sum >= target) { // [l,r]符合条件,维护res res = Math.min(res, r - l + 1); // l一直右移并统计,直至不满足条件 // 这里有个很值得思考的点:为什么l指针可以义无反顾地移动至不符合条件的l+1? // [l,r]合法;[l+1,r]不合法,而[l,r+1]及更长的不可能被统计因为只统计短的 // [l,r-1]以及更短的呢?右边界为r-1的情况已统计,因为l会直接移动到不合法且nums都为正数,因此窗口不可能继续缩小! // 所以此时l可以义无反顾地移动至l+1 sum -= nums[l++]; } } // 若没有窗口符合条件就是0 return res == Integer.MAX_VALUE ? 0 : res; } } |

为什么l指针可以义无反顾地移动至不符合条件的l+1?滑窗精髓所在->减少不必要的计算