??樊梓慕：個(gè)人主頁(yè)
???個(gè)人專欄：《C語(yǔ)言》《數(shù)據(jù)結(jié)構(gòu)》《藍(lán)橋杯試題》《LeetCode刷題筆記》《實(shí)訓(xùn)項(xiàng)目》《C++》《Linux》《算法》
??每一個(gè)不曾起舞的日子，都是對(duì)生命的辜負(fù)
目錄
前言
1.長(zhǎng)度最小的子數(shù)組
滑動(dòng)窗口類問題解題思路大綱：
2.無重復(fù)字符的最長(zhǎng)字串
3.最大連續(xù)1的個(gè)數(shù)Ⅲ
4.將 x 減到 0 的最小操作數(shù)（medium）
前言
本篇文章主要會(huì)講解滑動(dòng)窗口的解題思想，滑動(dòng)窗口實(shí)際上就是利用雙指針的基礎(chǔ)思想，并且利用單調(diào)性進(jìn)行解題的方法。
滑動(dòng)窗口所用到的雙指針是用來維護(hù)這個(gè)所謂的『 窗口』，所以這兩個(gè)指針是『 同向』且『 不回退』的，這也就決定了滑動(dòng)窗口解題的時(shí)間復(fù)雜度最多為O(2N) 即O(N)，所以滑動(dòng)窗口是一種非常優(yōu)秀的算法思想。
那么滑動(dòng)窗口思想具體的應(yīng)用，以及如何分析判斷是否適用滑動(dòng)窗口解題呢？
歡迎大家??收藏??以便未來做題時(shí)可以快速找到思路，巧妙的方法可以事半功倍。
=========================================================================文章來源地址http://www.zghlxwxcb.cn/news/detail-825716.html
GITEE相關(guān)代碼：??樊飛 (fanfei_c) - Gitee.com??
=========================================================================
1.長(zhǎng)度最小的子數(shù)組
209. 長(zhǎng)度最小的子數(shù)組 - 力扣（LeetCode）https://leetcode.cn/problems/minimum-size-subarray-sum/
給定一個(gè)含有?
n?個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù)?target?。找出該數(shù)組中滿足其總和大于等于?
target?的長(zhǎng)度最小的?連續(xù)子數(shù)組?[numsl, numsl+1, ..., numsr-1, numsr]?，并返回其長(zhǎng)度。如果不存在符合條件的子數(shù)組，返回?0?。
如果依照暴力枚舉的策略，解題思路大致如下：
利用雙指針，一個(gè)指針固定，移動(dòng)另一個(gè)指針，當(dāng)兩個(gè)指針中間的所有元素和大于等于目標(biāo)值target時(shí)，記錄此時(shí)的長(zhǎng)度，然后循環(huán)往復(fù)，求長(zhǎng)度最小值。
代碼如下：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
// 記錄結(jié)果
int ret = INT_MAX;
int n = nums.size();
// 枚舉出所有滿?和?于等于 target 的?數(shù)組[start, end]
// 由于是取到最?，因此枚舉的過程中要盡量讓數(shù)組的?度最?
// 枚舉開始位置
for (int start = 0; start < n; start++)
{
int sum = 0; // 記錄從這個(gè)位置開始的連續(xù)數(shù)組的和
// 尋找結(jié)束位置
for (int end = start; end < n; end++)
{
sum += nums[end]; // 將當(dāng)前位置加上
if (sum >= target) // 當(dāng)這段區(qū)間內(nèi)的和滿?條件時(shí)
{
// 更新結(jié)果，start 開頭的最短區(qū)間已經(jīng)找到
ret = min(ret, end - start + 1);
break;
}
}
}
// 返回最后結(jié)果
return ret == INT_MAX ? 0 : ret;
}
};可其實(shí)這其中有太多可以忽略掉的枚舉區(qū)間，我們來分析一下：
本題要求的是長(zhǎng)度最小子數(shù)組，所以此時(shí)一定是要更新left的位置即可，這就達(dá)到了不回退的目的。
注意：要在移動(dòng)left之前更新結(jié)果。
所以此類問題，我們可以將left和right中間的區(qū)域看作一塊窗口，該窗口不斷的向后移動(dòng)，直到right超出數(shù)組為止。
在這一過程中：
- right移動(dòng)導(dǎo)致元素進(jìn)入窗口的行為我們稱為『 進(jìn)入窗口』；
- left移動(dòng)導(dǎo)致元素離開窗口的行為我們稱為『 離開窗口』；
- 判斷l(xiāng)eft和right維護(hù)的窗口是否滿足題目條件我們稱為『 判斷』；
- 滿足題目條件時(shí)更新結(jié)果的行為我們稱為『 更新結(jié)果』。
所以以上這些步驟就構(gòu)成了『 滑動(dòng)窗口』類問題的解題思路。
滑動(dòng)窗口類問題解題思路大綱：
①left=0,right=0；
②進(jìn)入窗口；
③判斷；????????
????????離開窗口；
④更新結(jié)果；
其中更新結(jié)果取決于具體的題目要求，『 就題論題』。
比如本題就需要在『 離開窗口』之前『 更新結(jié)果』。
有了思路，畫圖獨(dú)立完成代碼，不要直接看博主的代碼。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int left=0,right=0;
int size=nums.size();
int sum=0;
int len=INT_MAX;
while(right<size)
{
sum+=nums[right];//進(jìn)入窗口
while(sum>=target)//判斷
{
len=min(len,right-left+1);//更新結(jié)果
sum-=nums[left++];//離開窗口
}
right++;
}
return len == INT_MAX ? 0 : len;
}
};2.無重復(fù)字符的最長(zhǎng)字串
3. 無重復(fù)字符的最長(zhǎng)子串 - 力扣（LeetCode）https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
給定一個(gè)字符串?
s?，請(qǐng)你找出其中不含有重復(fù)字符的?最長(zhǎng)子串?的長(zhǎng)度。
其實(shí)滑動(dòng)窗口類題目最重要的是弄清楚『 為什么』要使用滑動(dòng)窗口，而不是『 怎樣』適用滑動(dòng)窗口。
像本題，你是如何分析出要使用滑動(dòng)窗口的呢？
首先依據(jù)暴力枚舉的策略，同樣固定一個(gè)指針，移動(dòng)另一指針，搭配哈希表得到最長(zhǎng)字串：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ret = 0; // 記錄結(jié)果
int n = s.length();
// 1. 枚舉從不同位置開始的最?重復(fù)?串
// 枚舉起始位置
for (int i = 0; i < n; i++)
{
// 創(chuàng)建?個(gè)哈希表，統(tǒng)計(jì)頻次
int hash[128] = { 0 };
// 尋找結(jié)束為?
for (int j = i; j < n; j++)
{
hash[s[j]]++; // 統(tǒng)計(jì)字符出現(xiàn)的頻次
if (hash[s[j]] > 1) // 如果出現(xiàn)重復(fù)的
break;
// 如果沒有重復(fù)，就更新 ret
ret = max(ret, j - i + 1);
}
}
// 2. 返回結(jié)果
return ret;
}
};注意：因?yàn)轭}目說明都為字符，所以我們可以創(chuàng)建一個(gè)128大小的數(shù)組用來模擬哈希表，沒有必要真的申請(qǐng)一個(gè)哈希表出來。?
然后才能依據(jù)這一暴力枚舉的底子我們做優(yōu)化。
思路：
當(dāng)right指向重復(fù)字符時(shí)，我們是否需要直接讓right回退，left++呢？
其實(shí)如果right指向重復(fù)字符了，那么就證明此時(shí)就是left開頭代表的窗口的最長(zhǎng)字串了（因?yàn)樵谶@之前right沒有指向重復(fù)字符），所以此時(shí)不需要移動(dòng)right，而應(yīng)該移動(dòng)left直到?jīng)]有重復(fù)字符為止，然后再移動(dòng)right即可。
- 如果這個(gè)字符出現(xiàn)的頻次超過1 ，說明窗口內(nèi)有重復(fù)元素，那么就從左側(cè)開始劃出窗口，直到這個(gè)元素的頻次變?yōu)?，然后再更新結(jié)果。
- 如果沒有超過1 ，說明當(dāng)前窗口沒有重復(fù)元素，可以直接更新結(jié)果。
所以『 更新結(jié)果』我們可以統(tǒng)一放在『 判斷』的外面。
?有了思路，畫圖獨(dú)立完成代碼，不要直接看博主的代碼。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int hash[128]={0};
int left=0,right=0,len=0;
int n=s.size();
while(right<n)
{
hash[s[right]]++;//進(jìn)入窗口
while(hash[s[right]]>1)//判斷
hash[s[left++]]--;//離開窗口
len=max(len,right-left+1);//更新結(jié)果
right++;
}
return len;
}
};3.最大連續(xù)1的個(gè)數(shù)Ⅲ
1004. 最大連續(xù)1的個(gè)數(shù) III - 力扣（LeetCode）https://leetcode.cn/problems/max-consecutive-ones-iii/description/
給定一個(gè)二進(jìn)制數(shù)組?
nums?和一個(gè)整數(shù)?k，如果可以翻轉(zhuǎn)最多?k?個(gè)?0?，則返回?數(shù)組中連續(xù)?1?的最大個(gè)數(shù)?。
?雖然題目中說是要翻轉(zhuǎn)數(shù)字，但我們要的最終結(jié)果與翻轉(zhuǎn)無關(guān)，何況如果真的實(shí)現(xiàn)翻轉(zhuǎn)反而變得復(fù)雜，所以這里我們沒有必要真的翻轉(zhuǎn)。
仔細(xì)閱讀題目，其實(shí)就是求數(shù)組中?段最長(zhǎng)的連續(xù)區(qū)間，要求這段區(qū)間內(nèi) 0 的個(gè)數(shù)不超過 k 個(gè)。
既然是連續(xù)區(qū)間，可以考慮使用『 滑動(dòng)窗口』來解決問題。
思路：
設(shè)置一個(gè) 0 計(jì)數(shù)器 zero。
如果 right 遇到 0，我們應(yīng)該讓 zero ++ ，如果 right 遇到 1，直接跳過即可，這就是『 進(jìn)入窗口』。
判斷什么呢？當(dāng)然是『 判斷』zero是否超過 k，如果超過 就『 離開窗口』，每輪『 更新結(jié)果』。
?有了思路，畫圖獨(dú)立完成代碼，不要直接看博主的代碼。
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int left=0,right=0,zero=0;
int n=nums.size();
int ret=0;
while(right<n)
{
if(nums[right]==0)//進(jìn)入窗口
zero++;
while(zero>k)//判斷
{
if(nums[left++]==0)//離開窗口
zero--;
}
ret=max(ret,right-left+1);//更新結(jié)果
right++;
}
return ret;
}
};4.將 x 減到 0 的最小操作數(shù)（medium）
1658. 將 x 減到 0 的最小操作數(shù) - 力扣（LeetCode）https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/
給你一個(gè)整數(shù)數(shù)組?
nums?和一個(gè)整數(shù)?x?。每一次操作時(shí)，你應(yīng)當(dāng)移除數(shù)組?nums?最左邊或最右邊的元素，然后從?x?中減去該元素的值。請(qǐng)注意，需要?修改?數(shù)組以供接下來的操作使用。如果可以將?
x?恰好?減到?0?，返回?最小操作數(shù)?；否則，返回?-1?。
閱讀題目后，我們發(fā)現(xiàn)解決方案可能比較復(fù)雜，因?yàn)榧扔锌赡軓淖竺?，也有可能從右面，還有可能一左一右等等，這么多復(fù)雜的情況，所以我們需要嘗試對(duì)問題做轉(zhuǎn)化，這也就是『 正難則反』的思路。?
如上圖，我們可以求?target 這一區(qū)域最長(zhǎng)時(shí)，那么此時(shí)就對(duì)應(yīng)著最小操作數(shù)，最小操作數(shù)就等于數(shù)組元素個(gè)數(shù)減去target區(qū)域的元素個(gè)數(shù)。
所以我們成功轉(zhuǎn)化出『 滑動(dòng)窗口』問題。
- 如果?sum < target ，右移右指針，直至變量和大于等于 target ，或右指針已經(jīng)移到頭；
- 如果?sum > target ，右移左指針，直至變量和小于等于?target ，或左指針已經(jīng)移到頭；
- 如果經(jīng)過前兩步的左右移動(dòng)使得?sum == target ，維護(hù)滿足條件數(shù)組的最大長(zhǎng)度，并讓下個(gè)元素進(jìn)入窗口；
?有了思路，畫圖獨(dú)立完成代碼，不要直接看博主的代碼。
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int sum=0;
for(int a : nums)
{
sum+=a;
}
int target = sum-x;
if(target<0) return -1;//處理細(xì)節(jié)
int left=0,right=0,tmp=0;
int n=nums.size();
int len=-1;
while(right<n)
{
tmp+=nums[right];//進(jìn)入窗口
while(tmp > target)//判斷
tmp-=nums[left++];//離開窗口
if(tmp==target)
len=max(len,right-left+1);//更新結(jié)果
right++;
}
if(len==-1) return len;
else return n-len;
}
};=========================================================================
如果你對(duì)該系列文章有興趣的話，歡迎持續(xù)關(guān)注博主動(dòng)態(tài)，博主會(huì)持續(xù)輸出優(yōu)質(zhì)內(nèi)容
??博主很需要大家的支持，你的支持是我創(chuàng)作的不竭動(dòng)力??
??~ 點(diǎn)贊收藏＋關(guān)注 ~??文章來源：http://www.zghlxwxcb.cn/news/detail-825716.html
=========================================================================
到了這里，關(guān)于【算法】基礎(chǔ)算法002之滑動(dòng)窗口（一）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
