1.長度最小的子數組

leetcode 209.長度最小的子數組

看到這個題目，第一眼肯定想到的是暴力枚舉，那我們就來枚舉以下試試：

很明顯，暴力枚舉的方式會超時。

那有沒有哪里能優化一下，讓它不超時呢？我們來分析一下：

在暴力枚舉中，我們的 right 每次都會回到left位置的下一個，然后和 left 一起重新枚舉。

優化枚舉具體步驟如下：

在上面的枚舉過程中，我們的藍色框就像是一個滑動的、大小不固定的窗口，我們稱這種方式叫做滑動窗口

對與滑動窗口而言，無非就以下幾個步驟：

每個題目窗口的起始、更新結果的位置是不固定的，具體情況具體分析。

按照滑動窗口的方法，我們的代碼就不會超時啦。

簡單分析以下時間復雜度：從代碼看好像是O(n²)，但是由于我們滑動窗口的思想，兩個指針是同向遍歷，而且不會回退；當right指針結束時，循環結束，所以它的時間復雜度是O(n)。

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int ret = INT_MAX;int n = nums.size();int sum = 0;for(int left = 0, right = 0; right < n; right++)//right后移{//進窗口sum += nums[right];//判斷窗口while(sum >= target){//符合條件，更新結果ret = min(ret,right - left + 1);sum -= nums[left];//出窗口left++;}  }if(ret == INT_MAX)return 0;elsereturn ret;}
};

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

leetcode 3.無重復字符的最長字串

這一題首先想到的方法無疑就是枚舉，然后統計每個字符出現的次數；如果一個字符出現了兩次，那么當前字符對應的字符串就是最長子串

我們發現，暴力枚舉法也可以過

那有沒有更優的解法呢？我們來分析一下

上述解法不就是滑動窗口嗎？

此時的時間復雜度O(n)是不是比暴力枚舉O(n²)更加優秀了

class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.size();int hash[128] = { 0 };int ret = 0;for(int left = 0, right = 0; right < n; right++){hash[s[right]]++;//入窗口，先記錄當前while(hash[s[right]] > 1)//若s[right]重復{hash[s[left]]--;//出窗口left++;}ret = max(ret,right - left + 1);//更新結果}return ret;}
};

3.最大連續1的個數III

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

分析題目可知，其中0可以翻轉的意思就是：0可以當作1來用。那我們的目標就是找一段包含1的個數最大連續的區間，該區間中0的個數不可以超過k。

這一題的暴力枚舉法就不演示了，我們直接上滑動窗口。


這樣我們的代碼就過咯

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n = nums.size();int zero = 0;//統計0的個數int ret = 0;for(int left = 0, right = 0; right < n; right++){//進窗口，判斷是否是0if(nums[right] == 0)zero++;//判斷0的個數是否大于kwhile(zero > k){//判斷是否是0出窗口if(nums[left] == 0)zero--;left++;}//更新結果ret = max(ret,right-left+1);}return ret;}
};

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

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

通過讀題我們可以發現，它一會是左邊，一會是右邊，是不是很難控制；那應該怎么做呢？
正難則反

• 我們在數組中找一塊連續的區間，數組中去除該連續區間的內容，剩下的內容剛好等于x時，那我們是不是就找到了一種情況
• 該連續區間就是數組中元素的總和減去x
• 當在數組中找到的一塊連續區間最長時，我們就找到了最佳的解決方案。

還是像前面的題目一樣，使用滑動窗口。

class Solution {
public:int minOperations(vector<int>& nums, int x) {int ret = 0;int total = 0;int n = nums.size();for(auto e : nums)total += e; //求數組的和int target = total - x; //target為要找的連續區間的總大小if(target < 0)//細節return -1;if(total == x)return n;int sum = 0;for(int left = 0, right = 0; right < n; right++){sum += nums[right];//進窗口while(sum > target){sum -= nums[left];left++;}if(sum == target)//找到目標區間，取長的一個ret = max(ret,right - left + 1);}if(ret == 0)return -1;elsereturn n - ret;}
};

5.水果成籃

leetcode 904.水果成籃

這個題目這么長，它表達的是什么意思呢？

只有兩個籃子，籃子里的水果只能有兩種，并且不能跨越樹木，求你所經過的樹的最多的個數。
那又是求一段連續區間的長度，我們可以使用滑動窗口

那我怎么知道當前摘的水果有幾種呢？----使用哈希表統計

我們可以發現，使用哈希表的消耗還是挺大的，能不能再優化一下呢？

由題目要求可知，種類是小于10⁵的，所以我們可以直接使用一個數組+一個變量（記錄種類）

這樣我們的效率就提升了很多。

class Solution {
public:int totalFruit(vector<int>& fruits) {int n = fruits.size();int ret = 0;int hash[100000] = { 0 };int kinds = 0;for(int left = 0, right = 0; right < n; right++){if(hash[fruits[right]] == 0)//判斷是否是新種類水果kinds++;hash[fruits[right]]++;//進窗口while(kinds > 2)//判斷總類是否大于2{hash[fruits[left]]--;//出窗口if(hash[fruits[left]] == 0)kinds--;  //去除該種類left++;}ret = max(ret,right - left + 1);}return ret;}
};

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

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

分析題目可知，就是在s串中找出p串（p串中的字符順序可打亂）。
那我們就可以找一個長度和p相等，且字符種類、個數和p串相等的子串即可。

所以我們可以使用兩個哈希表，分別統計p串和s串中字符的種類和個數。

那我們先使用暴力枚舉的方式試一下：

那兩個哈希表是如何進行比較的呢？

1. 首先使用hash1記錄p串中字符的類型個數
2. 遍歷s，找長度和p相等的子串，同時hash2存放當前字符
   a、若hash2[right] <= hash1[right]時，“有效字符”種類增加
   b、若hash2[right] > hash2[right]，“有效字符”種類不變

暴力枚舉的方式確實可以過，但效率比較低下。
既然是找一段連續的區間，那能不能使用滑動窗口呢？我們來試一下

這樣我們的效率就高很多了

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int len = p.size();int hash1[128] = { 0 };for(auto e: p)hash1[e]++;//統計p串的種類int n = s.size();int hash2[128] = { 0 };//統計子串種類int kinds = 0;int tmp = 0;for(int left = 0,right = 0; right < n ; right++){hash2[s[right]]++; //進窗口tmp++;//子串長度增加if(hash2[s[right]] <= hash1[s[right]])kinds++;//"有效字符"種類增加if(tmp > len){if(hash2[s[left]] <= hash1[s[left]])kinds--;//left位置為“有效字符”，種類減少hash2[s[left]]--;tmp--;left++;}if(tmp == len)if(kinds == len)ret.push_back(left);}return ret;}
};

7.串聯所有單詞的子串

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

這一題和前一道題目類似，只不過這里是將字符換成了字符串而已。因此我們還是使用：滑動窗口+哈希表的方式解決。

解題步驟：

1. 先使用hash1統計words中字符串的種類
2. 使用滑動窗口(由于字符串的長度是固定的，所以可以直接跳躍長度)
   a、定義起始：left、right
   b、字符串進窗口，需要使用字符串的函數substr進行裁剪
   c、判斷字符串的種類
   ? 是否出窗口
   ? 更新結果

然而，代碼只過了一部分，分析一下它的測試用例發現，

這樣代碼就過啦！

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string,int> hash1;for(auto& e : words)hash1[e]++;//統計要求的字符串種類int n = s.size();int len = words[0].size();//固定的字符串長度int m = words.size();//數組長度for(int i=0; i < len; i++){unordered_map<string,int> hash2;int count = 0;for(int left = i, right = i; right <= n -len; right+= len){string in = s.substr(right,len);//裁剪字符串hash2[in]++;//進窗口if(hash2[in] <= hash1[in])count++;//統計當前字符串數量if(right - left + 1 > m*len)//判斷字符串數量是否大于字符數組{string 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.最小覆蓋子串

leetcode 76.最小覆蓋子串

該題和上一題的解題思路差不多，也是在s串中找t串的全部字符，只不過這里要將找到的字符串的最小的一個返回而已。

我們依舊使用滑動窗口+哈希表的方式解決。

1. 使用hash1統計t串中字符的種類和數量
2. 滑動窗口：定義起始位置 left, right
   a、進窗口
   b、判斷是否出窗口
   c、更新結果（僅需記錄串的起始位置和長度，最后在切割子串）

在代碼中在記錄字符串的起始位置和長度即可，這樣我們的代碼就過啦。

class Solution {
public:string minWindow(string s, string t) {int hash1[128] = { 0 };for(auto e : t)hash1[e]++;//統計t串的字符種類和數量int m = t.size();int n = s.size();int hash2[128] = { 0 };int count = 0;int start = 0;int len = INT_MAX;for(int left = 0, right = 0; right < n; right++){hash2[s[right]]++;//進窗口if(hash2[s[right]] <= hash1[s[right]])//是否更新有效字符count++;while(count >= m)//是否出窗口{if(count == m)//找到符合種類的子串{//取長度小的一個int curlen = right - left + 1;if(curlen < len){start = left;len = curlen;}}//出窗口if(hash2[s[left]] <= hash1[s[left]])count--;hash2[s[left]]--;left++;}}if(len == INT_MAX)return "";elsereturn s.substr(start,len);}
};