呀哈嘍，我是結(jié)衣。
今天我們要學(xué)習(xí)的是一種新的算法，也是一種雙指針。不過他擁有一個全新的名字”滑動窗口“。
1.長度最小的子數(shù)組（medium）
題目鏈接：長度最小的子數(shù)組
題目描述：
思路
因為數(shù)組元素全為正整數(shù)，使得數(shù)組具有了一種單調(diào)性。以示例1為例子，2+3+1+2會大于7，那么我們好有必要繼續(xù)向后遍歷嗎？沒有必要，所以我們就會想到去掉前面的一個數(shù)變成3+1+2這樣也就小于7啦，于是我們就繼續(xù)遍歷數(shù)組，3+1+2+4又會大于7了我就重復(fù)剛剛的操作，我們遍歷完數(shù)組。
解題方法
又上面的思路我們可以想到定義兩個指針left和right，right來遍歷數(shù)組，left在后面跟著，是雙指針不過有了新的名字“滑動窗口”
在圖中我可以看到right和left共同維護著一段區(qū)間，而且right和left又可以移動，顧名思義就是滑動窗口
滑動窗口最重要的操作就是進窗口（移動right）判斷 出窗口（移動left） 更新結(jié)果。
只要這幾步就可以做出題目來。
要注意的數(shù)更新結(jié)果的位置是不確定的，要根據(jù)具體的題目要求。
Code
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int sum = 0,n = nums.size();
int len = INT_MAX;
for(int left = 0,right = 0;right<n;right++)//right++為進窗口
{
sum+=nums[right];
while(sum>=target)//判斷
{
len = min(len,right-left+1);//更新結(jié)果
sum-=nums[left];
left++;//出窗口
}
}
return len==INT_MAX?0:len;
}
};
2.無重復(fù)字符的最長子串（medium）
題目鏈接：無重復(fù)字符的最長子串
題目描述：
思路
當(dāng)我們不知道怎么寫之前，我們可以運用暴力的方法先考慮問題。遍歷字符串時（示例1），當(dāng)我們遍歷到第二個a時我們此時就出現(xiàn)了重復(fù)的字符，我們可以繼續(xù)遍歷，但那就沒有必要了。我們可以重新遍歷從第二個字符開始，再向后舉行遍歷，這樣的化時間復(fù)雜度肯定就是O（N^2）了這就是暴力，但是我不要忘了應(yīng)該怎么判斷重復(fù)字符，看肯定看的出來，可是對于計算機我們就要記錄一下字符了，所以我們就要運用到哈希表了。
解題方法
對于思路中的暴力解法，我們是可以做到很多優(yōu)化的，運用“滑動窗口”，使得時間復(fù)雜度變?yōu)镺（N）。
我們利用“滑動窗口”，來保證窗口中的元素一定不會重復(fù)就可以了，為了實現(xiàn)這個操作我們需要定義應(yīng)該哈希表。因為這里的數(shù)據(jù)全是字符，所以我們可以用int數(shù)組來映射就可以了。
然后就是滑動窗口的經(jīng)典操作：
滑動窗口最重要的操作就是進窗口（移動right）判斷 出窗口（移動left） 更新結(jié)果。
Code
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
int len = 0;
int hash[128] = {0};
for(int left = 0,right = 0;right<n;++right)//進窗口
{
hash[s[right]]++;
while(hash[s[right]]>1)
{
hash[s[left]]--;
left++;//出窗口
}
len = max(len,right-left+1);//更新結(jié)果
}
return len;
}
};
3.最大連續(xù)1的個數(shù) III（medium）
題目鏈接：最大連續(xù)1的個數(shù) III
題目描述：
思路
如果我們只是尋找最長的子字符串1，要考慮的東西就太多了。為了讓這個題目更加的簡單，我們應(yīng)該采用一種正難則反的思想，我們把問題轉(zhuǎn)化為尋找不超過k個0的最長子串。這樣做就簡單的多了，所以在寫編程題的時候如果一點想法都沒有不妨換個角度來想問題。
解題方法
當(dāng)我們把問題簡化之后，滑動窗口的想法就呼之欲出了，和前面一樣，我們要做的就是維護窗口里的元素。這次呢，我們要維護的就是窗口內(nèi)0元素不能超過k個。在此基礎(chǔ)上我們再運用滑動窗口的公式就可以解決問題了：進窗口（移動right）判斷 出窗口（移動left） 更新結(jié)果。
Code
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
//正難則反，我們把問題轉(zhuǎn)化為尋找不超過k個0的最長子串。
int zero = 0,len = -1;
for(int left = 0,right = 0;right<nums.size();++right)//進窗口
{
if(nums[right]==0) zero++;
while(zero>k)//條件判斷
{
if(nums[left]==0) zero--;
left++;//出窗口
}
if(zero == k)len = max(len,right-left+1);//更新結(jié)果
}
return len==-1?nums.size():len;
}
};
4.將x減到0的最小操作數(shù)（medium）
題目鏈接：將x減到0的最小操作數(shù)
題目描述
思路
同樣的，直接寫太麻煩了，要考慮的東西太過。還是正難則反，把問題轉(zhuǎn)化一下不就變成了求目標(biāo)值為sum-x最長子數(shù)組和，和第一題不就差不多了嗎？
解題方法
和第一題類似，運用滑動窗口解決，不過再滑動窗口操作之前我們要判斷一下sum-x是否為負數(shù)如果為負數(shù)的話，后面代碼就會溢出的。了解完成后還是那四步：進窗口（移動right）判斷 出窗口（移動left） 更新結(jié)果。
Code
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
//正難則反，表面上讓你找讓x減小到0的最小操作數(shù)，實際是可以轉(zhuǎn)化為求目標(biāo)值為sum-x最長子數(shù)組和。
int sum = 0;
for(auto num:nums) sum+=num;
int tar = sum-x;
if(tar<0)
return -1;
int sum_ = 0,res = -1;
for(int left = 0,right = 0;right<nums.size();++right)//進窗口
{
sum_+=nums[right];
while(sum_>tar)//條件判斷
{
sum_-=nums[left++];//出窗口
}
if(sum_==tar) res = max(res,right-left+1);//結(jié)果更新
}
return res == -1?res: nums.size()-res;
}
};
5.水果成籃（medium）
題目鏈接：水果成籃
題目描述：
思路
這道題的題目有點長，把他翻譯翻譯就是求最長不超過兩類樹的子數(shù)組。了解的這個，這道題就變得簡單了。至于如何判斷是否超過了兩類樹，又要用到哈希表了。
解題方法
寫題的關(guān)將就在于理解題目，我們要把題目轉(zhuǎn)化成我們熟悉的題目。就像這道題，轉(zhuǎn)化后就自然而然地想到了我們滑動窗口。不過就是再加上一個哈希表。我們建立一個哈希數(shù)組，在建立一個kinds來判斷窗口內(nèi)樹地種類。如何判斷呢？
Code
class Solution {
public:
int totalFruit(vector<int>& fruits) {
//題目可能有點難懂，翻譯一下就求最長不超過兩類樹的子數(shù)組。
int hash[100001] = {0};
int kinds = 0,n = fruits.size(),len = 0;
for(int left = 0,right = 0;right<n;++right)//進窗口
{
if(hash[fruits[right]]++==0) kinds++;
while(kinds>2)//條件判斷
{
if(--hash[fruits[left]]==0) kinds--;
left++;//出窗口
}
len = max(len,right-left+1);//更新結(jié)果
}
return len;
}
};
6.找到字符串中所有字母異位詞（medium）
題目鏈接：找到字符串中所有字母異位詞
題目描述：
思路
剛上手可能沒想法，那就嘗試暴力解法吧，依次遍歷字符串以示例1為例。
暴力加哈希可以解決但時間復(fù)雜度太高。
解題方法
優(yōu)化上面的暴力方法就需要滑動窗口了。不過這里我們著重要講的是如何利用哈希表來出來這種情況。我們定義了兩個哈希表。一個哈希1用來存放p字符串中的字符。哈希表2就用來存放s字符串里的字符。我們該如何判斷窗口內(nèi)的元素都是p中的呢？
方法一（直接比較哈希表）
因為字符串都是小寫字母，每次我們窗口里有p.size()的字符時我們就比較兩個哈希表，雖然每次比較都要遍歷哈希表，但是小寫字母只有26個時間復(fù)雜度度也就O（26*n）也是常數(shù)級別的可以忽略。
Code
class Solution {
public:
bool check(vector<int>hash,vector<int>hash_1)
{
for(int i = 0;i<26;++i)
{
if(hash[i]!=hash_1[i]) return false;
}
return true;
}
vector<int> findAnagrams(string s, string p) {
int n_p = p.size();
vector<int> hash_1(26,0);
for(auto tmp:p) hash_1[tmp-'a']++;
int n = s.size();
int left = 0,right = 0;
vector<int>hash(26,0);
vector<int>res;
while(right<n)
{
hash[s[right]-'a']++;
if(right>=n_p-1)
{
if(check(hash,hash_1))
res.push_back(left);
hash[s[left]-'a']--;
left++;
}
right++;
}
return res;
}
};
方法二（更優(yōu)）
我們利用一個count來記錄窗口內(nèi)p中字符串的個數(shù)。是p中的字符count就++，后續(xù)的出窗口也是如此，是p中的字符就count–。 這個方法的時間復(fù)雜度就是O(N)了
Code
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int hash_1[26] = {0};
int hash[26] = {0};
for(auto ch:p) hash_1[ch-'a']++;
int count = 0,n = s.size();
vector<int> res;
for(int left = 0,right = 0;right<n;++right)//進窗口
{
if(++hash[s[right]-'a']<=hash_1[s[right]-'a']) count++;
if(right-left+1>=p.size())//條件判斷
{
if(count==p.size()) res.push_back(left);//更新結(jié)果
if(hash[s[left]-'a']--<=hash_1[s[left]-'a']) count--;
left++;//出窗口
}
}
return res;
}
};
7.串聯(lián)所有單詞的子串（hard）
題目鏈接：串聯(lián)所有單詞的子串
題目描述：
思路
這題和上面的那道題是差不多的，把字符改成了字符串了，這樣的話我們之前的數(shù)組映射就不好用了。但是我們可以借助一個容器unordered_map。不過還有一點的不同，我們遍歷的次數(shù)發(fā)生了改變。
解題方法
在次數(shù)上的改變體現(xiàn)在因為現(xiàn)在是字符串了。len（word[0].size()）
還要注意的就是因為現(xiàn)在是字符串，所以我們的right和left可就是加len個長度了。
Code
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string,int> hash_1;
for(auto tmp:words) hash_1[tmp]++;
int len = words[0].size(),n = s.size();
vector<int>res;
for(int i = 0;i<len;++i)
{
unordered_map<string,int> hash;
int count = 0;
for(int left = i,right = i;right+len<=n;right+=len)//入窗口
{
string in = s.substr(right,len);
if(hash_1[in]&&++hash[in]<=hash_1[in]) count++;
if(right-left+len>=words.size()*len)//條件判斷
{
if(count==words.size()) res.push_back(left);//結(jié)果更新
string out = s.substr(left,len);
if(hash_1[out]&&hash[out]--<=hash_1[out]) count--;
left+=len;//出窗口
}
}
}
return res;
}
};
8.最小覆蓋子串（hard）
題目鏈接：最小覆蓋子串
題目描述：
思路
和前面兩題類似，大體上的步驟都一樣。
解題方法
可以和前面兩題用相似的寫法，定義兩個哈希表。然后用count來判斷窗口內(nèi)是否包含全部的t中元素。雖然我們的返回條件變啦。但是我們也可以不需要創(chuàng)建一個string來存儲最小的覆蓋子串，我們可以利用substr這個成員函數(shù)，只需要我們記錄一下初始的位置和長度就可以了。來試試吧。
Code
class Solution {
public:
string minWindow(string s, string t) {
int hash_1[128] = {0};
int hash[128] = {0};
for(auto ch:t) hash_1[ch]++;
int n = s.size(),count = 0,len = INT_MAX,begin = 0;
for(int left = 0,right = 0;right<n;++right)//進窗口
{
if(++hash[s[right]]<=hash_1[s[right]]) count++;
while(count>=t.size())//條件判斷
{
int old = len;
len = min(len,right-left+1);//結(jié)果更新
if(old!=len) begin = left;
if(hash[s[left]]--<=hash_1[s[left]]) count--;
left++;//出窗口
}
}
return len==INT_MAX?"":s.substr(begin,len);
}
};
總結(jié)規(guī)律
不知道你有沒有發(fā)現(xiàn)，我們的滑動窗口的代碼都差不多。我也是把每一道題都重新寫了一遍然后寫成了一樣的格式。
for(int left = 0,right = 0;right<n;++right)//進窗口
{
if(++hash[s[right]]<=hash_1[s[right]]) count++;
while(count>=t.size())//條件判斷
{
int old = len;
len = min(len,right-left+1);//結(jié)果更新
if(old!=len) begin = left;
if(hash[s[left]]--<=hash_1[s[left]]) count--;
left++;//出窗口
}
}
全是一層for循環(huán)來遍歷數(shù)組，里面的判斷肯是while循環(huán)也可能是if這取決于你要判斷的次數(shù)，然后我們的出窗口都是在判斷里面的，至于結(jié)果更新只有他的位置是變化的，所以我們在寫代碼前就要看看結(jié)果在哪里更新，這樣的話滑動窗口的問題就都可以解決了。
那么本篇博客就到這里結(jié)束了，如果存在錯誤希望得到您的指正。文章來源：http://www.zghlxwxcb.cn/news/detail-836782.html
完
文章來源地址http://www.zghlxwxcb.cn/news/detail-836782.html
到了這里，關(guān)于假期算法提升（帶你徹底掌握滑動窗口）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
