🌟快來參與討論💬，點贊👍、收藏?、分享📤，共創(chuàng)活力社區(qū)。 🌟

別再猶豫了！快來訂閱我們的算法每日雙題精講專欄，一起踏上算法學(xué)習(xí)的精彩之旅吧！💪

今天，咱們就一同來探究 “水果成籃” 和 “找到字符串中所有字母異位詞” 這兩道經(jīng)典題目，看看滑動窗口算法是如何在其中施展魔法的🧙?♂?。

---

目錄

💯水果成籃

📖題目描述

🧠講解算法原理

💻代碼實現(xiàn)（以 C++ 為例）

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

📖題目描述

?🧠講解算法原理

?💻代碼實現(xiàn)（以 C++ 為例）

---

💯水果成籃

題目鏈接👉【力扣】

📖題目描述

根據(jù)示例分析，該題的本質(zhì)就是：找出最長子數(shù)組的長度，子數(shù)組不超過倆種水果類型

🧠講解算法原理

解法一：

?我們用暴力解法寫一下，例如f=[1,2,3,2,2]

依次找出所以的情況👇

1. ?

代碼中我們利用哈希表列舉情況，用哈希表統(tǒng)計水果出現(xiàn)的類型數(shù)

解法二：

先分析

?當我們用暴力解法時，遇到如下情況👇，我們讓 left++ ，right 回到 left的位置，繼續(xù)列舉情況

當left++時，區(qū)間的?kinds 要么不變，要么減少一個

• 當kinds不變時，right沒有必要改變
• 當kinds減少時，right可以繼續(xù)向后移動

?因此我們可以用滑動窗口的解法，right不回退嘛

滑動窗口四大步：

1. ?left=0,right=0
2. 進窗口——right右移動的時候
3. 判斷? ? 出窗口——就是left右移動的時候
4. 更新結(jié)果

舉例： f=[1，2，1，2，3，2，3，3]

每次遍歷right,讓其放入hash表里面，判斷有沒有超出類型個數(shù)

當hash.length>2時出窗口

left右移動的時候，要根據(jù)某個水果種類的數(shù)量來進行移動，因此我們創(chuàng)建的hash表要有倆個參數(shù)，一個記錄種類，一個記錄個數(shù)

例如下面👇，我們要將left移動到3的前面

💻代碼實現(xiàn)（以 C++ 為例）

class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100001]={0};//統(tǒng)計窗口內(nèi)出現(xiàn)了多少種結(jié)果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;}
};

---

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

題目鏈接👉【力扣】

📖題目描述

?

?🧠講解算法原理

1.如何判斷倆個字符串是否是異位詞？

• 可以先排序再比較，但是時間復(fù)雜度為nlogn ，比較大
• 通過統(tǒng)計字符串中字符出現(xiàn)的個數(shù)也可以判斷，借助hash表即可

?2.解決問題

例如

暴力解法：?

計入p的長度m ，在S里依次比較?

?

優(yōu)化解法：

當字符串依次遍歷時，?，我們發(fā)現(xiàn)ba重復(fù)出現(xiàn)，所以我們只要將c從hash表移除，讓e加入hash表即可，滑動窗口

?

滑動窗口四大步：

1. ?left=0,right=0
2. 進窗口——right右移動的時候
3. 判斷? ? 出窗口——就是left右移動的時候
4. 更新結(jié)果

?

3.優(yōu)化：更新結(jié)果的判斷條件

利用變量count來統(tǒng)計窗口中“有效字符”的個數(shù)

使用一個數(shù)組targetCount來記錄字符串p中每個字母的出現(xiàn)次數(shù)，再使用一個數(shù)組windowCount來記錄當前窗口內(nèi)每個字母的出現(xiàn)次數(shù)。設(shè)一個變量valid來表示窗口內(nèi)有效字母的數(shù)量，初始值為0。?

然后，將right指針向右移動，每移動一次，就將新字母在windowCount中的計數(shù)加1，并檢查該字母的計數(shù)是否等于在targetCount中的計數(shù)，如果相等，則valid加1。當valid等于p中不同字母的數(shù)量時，說明當前窗口是一個字母異位詞。

?

此時，將left指針向右移動，同時更新windowCount和valid，直到valid小于p中不同字母的數(shù)量。在移動left指針的過程中，如果窗口內(nèi)的子串長度等于p的長度，就將left指針的索引加入到結(jié)果數(shù)組中。

?

重復(fù)上述步驟，直到right指針走到字符串s的末尾。最后，返回結(jié)果數(shù)組。

?💻代碼實現(xiàn)（以 C++ 為例）

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> result;// 如果s的長度小于p的長度，直接返回空結(jié)果if (s.length() < p.length()) return result;// 用于記錄字符串p中每個字母的出現(xiàn)次數(shù)vector<int> targetCount(26, 0);// 用于記錄當前窗口內(nèi)每個字母的出現(xiàn)次數(shù)vector<int> windowCount(26, 0);int valid = 0;// 初始化targetCount數(shù)組for (char c : p) {targetCount[c - 'a']++;}int left = 0, right = 0;while (right < s.length()) {int rightIndex = s[right] - 'a';// 將新字母在windowCount中的計數(shù)加1windowCount[rightIndex]++;// 如果該字母的計數(shù)小于等于在targetCount中的計數(shù)，說明該字母在窗口內(nèi)的數(shù)量還未超過p中該字母的數(shù)量，有效字母數(shù)量加1if (windowCount[rightIndex] <= targetCount[rightIndex]) {valid++;}// 當窗口大小大于p的長度時，移動left指針縮小窗口while (right - left + 1 > p.length()) {int leftIndex = s[left] - 'a';// 將left指針指向的字母在windowCount中的計數(shù)減1windowCount[leftIndex]--;// 如果該字母的計數(shù)小于在targetCount中的計數(shù)，說明該字母在窗口內(nèi)的數(shù)量已經(jīng)小于p中該字母的數(shù)量，有效字母數(shù)量減1if (windowCount[leftIndex] < targetCount[leftIndex]) {valid--;}left++;}// 如果有效字母數(shù)量等于p中不同字母的數(shù)量，說明當前窗口是一個字母異位詞，將left指針的索引加入結(jié)果數(shù)組if (valid == p.length()) {result.push_back(left);}right++;}return result;}
};

---

我以后還會對 算法 相關(guān)知識進行更多的創(chuàng)作，歡迎大家關(guān)注我，一起探索 算法 的奇妙世界😜

👉【A Charmer】