作者：fuxuemingzhu
鏈接：https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/fen-xiang-hua-dong-chuang-kou-mo-ban-mia-f76z/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

LeetCode刷題：滑動窗口模板以及典型例題

• 滑動窗口模板
• 1004. 最大連續(xù)1的個數(shù) III

滑動窗口模板

《挑戰(zhàn)程序設(shè)計競賽》這本書把滑動窗口形象地叫做【蟲取法】。因為滑動窗口的兩個指針移動的過程和蟲子爬動的過程非常像：前腳不動，把后腳移動過來；后腳不動，把前腳向前移動。

def findSubArray(nums):N = len(nums) # 數(shù)組/字符串長度left, right = 0, 0 # 雙指針，表示當(dāng)前遍歷的區(qū)間[left, right]，閉區(qū)間sums = 0 # 用于統(tǒng)計 子數(shù)組/子區(qū)間 是否有效，根據(jù)題目可能會改成求和/計數(shù)res = 0 # 保存最大的滿足題目要求的 子數(shù)組/子串 長度while right < N: # 當(dāng)右邊的指針沒有搜索到 數(shù)組/字符串 的結(jié)尾sums += nums[right] # 增加當(dāng)前右邊指針的數(shù)字/字符的求和/計數(shù)while 區(qū)間[left, right]不符合題意：# 此時需要一直移動左指針，直至找到一個符合題意的區(qū)間sums -= nums[left] # 移動左指針前需要從counter中減少left位置字符的求和/計數(shù)left += 1 # 真正的移動左指針，注意不能跟上面一行代碼寫反# 到 while 結(jié)束時，我們找到了一個符合題意要求的 子數(shù)組/子串res = max(res, right - left + 1) # 需要更新結(jié)果right += 1 # 移動右指針，去探索新的區(qū)間return res

滑動窗口中用到了左右兩個指針，它們移動的思路是：以右指針作為驅(qū)動，拖著左指針向前走。右指針每次只移動一步，而左指針在內(nèi)部while循環(huán)中每次可能移動多步。右指針是主動前移動，探索未知的新區(qū)域；左指針是被迫移動，負(fù)責(zé)尋找滿足題意的區(qū)間。

模板的整體思想是：

定義兩個指針left和right，分別指向區(qū)間的開頭和結(jié)尾，注意是閉區(qū)間；定義sums用來統(tǒng)計該區(qū)間內(nèi)的各個字符出現(xiàn)次數(shù)；

第一重while循環(huán)是為了判斷right指針的位置是否超出了數(shù)組邊界；當(dāng)right每次到了新位置，需要增加right指針的求和或計數(shù)；

第二重while循環(huán)是讓left指針向右移動到[left,right]區(qū)間符合題意的位置；當(dāng)left每次移動到新位置，需要減少left指針的求和或計數(shù)；

在第二重while循環(huán)之后，成功找到一個符合題意的[left,right]區(qū)間，題目要求最大的區(qū)間長度，因此更新res為max(res，當(dāng)前區(qū)間的長度)；

right指針每次向右移動一步，開始探索新的區(qū)間；

1004. 最大連續(xù)1的個數(shù) III

https://leetcode-cn.com/problems/max-consecutive-ones-iii/

解題思路

重點：題意轉(zhuǎn)換。把「最多可以把 K 個 0 變成 1，求僅包含 1 的最長子數(shù)組的長度」轉(zhuǎn)換為 「找出一個最長的子數(shù)組，該子數(shù)組內(nèi)最多允許有 K 個 0 」。

經(jīng)過上面的題意轉(zhuǎn)換，我們可知本題是求最大連續(xù)子區(qū)間，可以使用滑動窗口方法。滑動窗口的限制條件是：窗口內(nèi)最多有 K 個 0。

代碼思路

• 使用left和right兩個指針，分別指向滑動窗口的左右邊界。
• right主動右移動：right指針每次移動一步。當(dāng)A[right]為0，說明滑動窗口內(nèi)增加了一個0；
• left被動右移動：判斷此時窗口內(nèi)0的個數(shù)，如果超過了K，則left指針被迫右移動，直至窗口內(nèi)的0的個數(shù)小于等于K為止。
• 滑動窗口長度的最大值即為所求。

class Solution {public int longestOnes(int[] A, int K) {int N = A.length;int res = 0;int left = 0, right = 0;int zeros = 0;while (right < N) {if (A[right] == 0)zeros ++;while (zeros > K) {if (A[left++] == 0) zeros --;}res = Math.max(res, right - left + 1);right ++;}return res;} }

總結(jié)

以上是生活随笔為你收集整理的LeetCode刷题：滑动窗口模板以及典型例题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。