個人主頁 ： zxctscl
專欄 【C++】、 【C語言】、 【Linux】、 【數據結構】、 【算法】
如有轉載請先通知

前言

1 209. 長度最小的子數組

1.1 分析

暴力枚舉出所有的子數組和，發現可以利用雙指針來解決。
這里雙指針是同向的，就能優化為滑動窗口。
(1)先初始化left和right，用left和right來標記這個窗口的左右區間
(2)進窗口
(3)判斷決定是否出窗口

1.2 代碼

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums){int n=nums.size();int sum=0,len=INT_MAX;for(int left=0,right=0;right<n;right++){sum+=nums[right];while(sum>=target){len=min(len,right-left+1);sum-=nums[left++];}}return len==INT_MAX?0:len;}
};

2 3. 無重復字符的最長子串

2.1 分析

暴力枚舉利用雙指針加哈希表：
left在起始位置，right遍歷，當字符不在哈希表里，就添加；當字符在時候，right就停止遍歷，把此時的字符長度更新一下；再把left移動到與right遍歷到相同字符的那個位置的后面一個，然后right再繼續移動。

使用滑動窗口來實現：

(1)先初始化left和right，用left和right來標記這個窗口的左右區間
(2)進窗口，讓字符進入哈希表
(3)判斷：當窗口內出現重復字符出窗口，再從哈希表中刪除該字符。
再更新長度

2.2 代碼

class Solution 
{
public:int lengthOfLongestSubstring(string s) {int hash[128]={0};//數組模擬哈希表int n=s.size();int ret=0;for(int left=0,right=0;right<n;right++){hash[s[right]]++;//進窗口while(hash[s[right]]>1)//判斷{hash[s[left++]]--;//出窗口}ret=max(ret,right-left+1);}return ret;}
};

3 1004. 最大連續1的個數 III

3.1 分析

只要翻轉的0個數小于等于k就行。
如果按照題目要求翻轉，是比較麻煩的，但可以等價處理為：找一個區間滿足0的次數不超過k就行。
也就是找出最長子數組，這個子數組的0不超過k個
解法一：暴力枚舉所有子數組，加上一個計數器zero
優化一下

固定left，right向后移動，right遇到0統計一個計數器，計數器等于3時候，停止枚舉，就是這個區間最優解。

利用滑動窗口來解決問題：

1. 先定義兩個指針left=0,right=0
2. 進窗口，如果right遇到1，無視；遇到0，zero+1
3. 判斷：zero>k 就 出窗口
   判斷完后更新結果

3.2 代碼

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

4 1658. 將 x 減到 0 的最小操作數

4.1 分析

發現既有左邊刪除，又有右邊的的，不好操作，此時可以找一個連續區域，恰好所有元素的和(sum)等于sum-x

1. 先定義兩個指針left=0,right=0
2. 進窗口，sum+=nums[right]
3. 判斷：sum>target
   出窗口：sum-=nums[left]
   當sum==target判斷完后更新結果

4.2 代碼

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;int ret=-1;for(int left=0,right=0,tmp=0;right<nums.size();right++){tmp+=nums[right];while(tmp>target){tmp-=nums[left++];}if(tmp==target)ret=max(ret,right-left+1);}if(ret==-1)return -1;else{return nums.size()-ret;}}
};

5 904. 水果成籃

5.1 分析

題目意思就是：找出一個最長子數組，子數組中不超過兩種類型的水果。

解法一：暴力枚舉+哈希表：從某一個位置開始，建立一個哈希表，暴力枚舉時候，遍歷一個放哈希表一個，當表中數據超過2時候，就出現了多余水果，前面的區間就是最優解。

優化：固定一個位置left，right遍歷數組放在哈希表中，直到某一個位置，right再向右遍歷時候，水果種類就超過2，此時這段區間就是最優解。此時，當left向后移動一位時，種類數目（kinds)可能會出現兩種情況：（1）kinds不變，那么right也不變；（2）kinds變小,此時right就可以向右移動

解法二：滑動窗口

1. 先定義兩個指針left=0,right=0
2. 進窗口，遍歷數組放哈希表里，哈希表里面放水果種類及對應數量
3. 判斷：如果哈希表長度大于2而且它對應數量為0時候就出窗口
   更新結果
   

5.2 代碼

class Solution {
public:int totalFruit(vector<int>& fruits){int hash[100001]={0};int ret=0;for(int left=0,right=0,kinds=0;right<fruits.size();right++){if(hash[fruits[right]]==0)kinds++;hash[fruits[right]]++;while(kinds>2){hash[fruits[left]]--;if(hash[fruits[left]]==0)kinds--;left++;}ret=max(ret,right-left+1);}return ret;}
};

6 438. 找到字符串中所有字母異位詞

6.1 分析

如何快速判斷兩個字符串是否是異位詞？
兩個字符串的構成是一樣的，利用哈希表，遍歷兩個字符串分別放在哈希表中，對比兩個哈希表中字符出現的個數是否相等就行，相等就是，反之就不是。

算法：
暴力+哈希表
把p字符串先放入哈希表中，再到s中找相等長度的區間子串放在另一個哈希表中，比較一個，相等就把起始位置放在結果中。

當s中與p等長區間中比較后，不是異位詞，此時就把s放在哈希表中的第一個字符刪除，再加上區間長度下一個位置字符就行。

p長度為m，hash1記錄p的字符情況，hash2記錄s中一段區間的字符情況
滑動窗口+哈希表

1. 先定義兩個指針left=0,right=0
2. 進窗口，(哈希表遍歷s)hash2[in]++
3. 判斷：right-left+1>m，就出窗口，再hash1[out]–（對應s中的字符得刪除）

當兩個哈希表里面存在信息是否一致時候，就更新結果

優化：更新判斷條件
利用變量count來統計窗口中有效字符的個數
right遍歷時候，c加入哈希表2中，與hash1中c個數相比較，都是1，此時count=1；
right繼續向后面移動，遇到c加入hash2中，這個時候hash2中c=2，,比hash1中c=1大，這個時候count不更新；
right繼續向后移動，b放入hash2中，比較hash1中b=1，此時count=2，而且s遍歷的區間長度等于p的長度，此時有效字符個數count=2不等于p的長度；
right繼續右移，這是區間長度大于p的，left就右移，a放到哈希表2中a=1，count=3，刪除c（hash2中c=2，刪除的這個c是無效字符），hash2中c=1；

進窗口：進窗口后比較hash2[in]<=hash1[in]此時count++;
出窗口：出去前 hash2[out]<=hash1[out]此時count–;
更新結果：count=m

6.2 代碼

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int hash1[26]={0};//統計pfor(auto x:p)hash1[x-'a']++;int hash2[26]={0};//sint m=p.size();for(int left=0,right=0,count=0;right<s.size();right++){char in=s[right];hash2[in-'a']++;if(hash2[in-'a']<=hash1[in-'a'])count++;if(right-left+1>m){char out=s[left++];if(hash2[out-'a']<=hash1[out-'a'])count--;hash2[out-'a']--;}if(count==m)ret.push_back(left);}return ret;}
};

7 30. 串聯所有單詞的子串

7.1 分析

與上面串聯所有單詞的子串類似，只不過把字符換成字符串，解法類似。
把題目給的words中的字符串看做一個一個整體，像下面這樣

與上面不同的是：
（1）哈希表：不能向上面一樣用數組來實現，這里存字符串，得用unordered_map<string,int> hash
（2）left與right指針的移動：移動的步長是單詞的長度(len)
（3）滑動窗口指向的次數：單詞可能是從s的第一個位置開始劃分，也可能是第二個位置，也可能是第三個位置：

滑動窗口執行len次

7.2 代碼

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string,int> hash1;for(auto& x:words)hash1[x]++;int len=words[0].size(),m=words.size();for(int i=0;i<len;i++){unordered_map<string,int> hash2;for(int left=i,right=i,count=0;right+len<=s.size();right+=len){string in=s.substr(right,len);//進窗口+維護counthash2[in]++;if(hash2[in]<=hash1[in])count++;//判斷if(right-left+1>len*m){//出窗口+維護countstring out=s.substr(left,len);if(hash2[out]<=hash1[out])count--;hash2[out]--;left+=len;}//更新結果if(count==m)ret.push_back(left);}}return ret;}
};

8 76. 最小覆蓋子串

8.1 分析

與串聯所有單詞的子串類似，

解法一：暴力枚舉+哈希表
在連續區間中找符合要求的ABC出現次數

在符合連續區間中，left右移right會出現兩種情況

解法二：滑動窗口

1. 先定義兩個指針left=0,right=0
2. 進窗口，hash2[in]++
3. 判斷：對比一下hash2有效字符大于等于hash1有效字符就更新結果起始位置，最短長度；再出窗口，hash2[out]–

優化：利用變量count來統計窗口中有效字符的種類
（1）.進窗口 進之后當hash2[in]==hash1[in]此時count++
（2） 出窗口 出之前，當hash2[out]==hash1[out]，count--
（3）判斷 count==hash.size()

8.2 代碼

class Solution {
public:string minWindow(string s, string t) {int hash1[128]={0};int kinds=0;//統計有效字符有多少種for(auto& x:t){if(hash1[x]==0) kinds++;hash1[x]++;}int hash2[128]={0};int minlen=INT_MAX,begin=-1;for(int left=0,right=0,count=0;right<s.size();right++){char in=s[right];hash2[in]++;if(hash2[in]==hash1[in])count++;//進窗口+維護countwhile(kinds==count){if(right-left+1<minlen){minlen=right-left+1;begin=left;}char out=s[left++];if(hash2[out]--==hash1[out])count--;}}if(begin==-1)return "";else return s.substr(begin,minlen);}
};