柚子快報激活碼778899分享：算法——滑動窗口

http://yzkb.51969.com/

目錄

1. 什么是滑動窗口？

2. 滑動窗口的大致解題流程

3. 應(yīng)用實例

1.?無重復(fù)字符的最長子串

2.?最大連續(xù)1的個數(shù)

3.?將x減到0的最小操作數(shù)

4. 水果成籃

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

6.?串聯(lián)所有單詞的子串

7. 最小覆蓋子串

1. 什么是滑動窗口？

滑動窗口算法是一種解決數(shù)組或列表中子數(shù)組或子序列問題的有效方法。該算法通過定義一個窗口，然后在數(shù)據(jù)結(jié)構(gòu)上滑動該窗口，逐步處理數(shù)據(jù)，以解決特定類型的問題。其基本思想是維護一個窗口，初始時窗口覆蓋數(shù)組中的一部分元素，然后通過滑動窗口來依次處理每個子數(shù)組。在每次窗口滑動時，可以通過添加新元素和刪除舊元素來更新窗口的內(nèi)容，以在O(1)時間內(nèi)完成操作。

2. 滑動窗口的大致解題流程

滑動窗口實際上是雙指針算法的一個延伸，它特指雙指針算法中的同向雙指針，在這里我們以一道例題來講解滑動窗口類型的大致解題流程，例題如下：209. 長度最小的子數(shù)組 - 力扣（LeetCode）

由于在實際的做題中，我們并不能總是直接判斷這道題能用什么算法，因此我們可以先用暴力解法解決這道題，即固定一個左指針，從左指針的位置向右遍歷數(shù)組，遍歷到和為target為止（第一個即可），隨后將左指針右移，再次執(zhí)行上述操作，隨時統(tǒng)計最小的區(qū)間，稍微分析這個算法我們可以發(fā)現(xiàn)它的時間復(fù)雜度是O(N^2)的，在這個過程中我們可以看到，整個數(shù)組是嚴格單調(diào)的且指針移動方向是相同的，此時我們就可以采取滑動窗口的思想來解決，滑動窗口一般流程如下

1. 進窗口

2. 判斷

? ? ? ? 出窗口

3. 在合適的位置更新結(jié)果

在這道題中我們可以發(fā)現(xiàn)，當右指針處于一個新位置時，將其所在元素入窗口，直到sum（窗口內(nèi)元素和）>= target時，將左指針位置出窗口，并記錄當前區(qū)間 ，稍加分析可以發(fā)現(xiàn)更新結(jié)果的位置應(yīng)該在出窗口前，這樣的話我們可以得到如下代碼

class Solution

{

public:

int minSubArrayLen(int target, vector& nums)

{

int len = INT_MAX;

int n = nums.size(), sum = 0;

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;

}

};

3. 應(yīng)用實例

1.?無重復(fù)字符的最長子串

題目鏈接：3. 無重復(fù)字符的最長子串 - 力扣（LeetCode）

解析：分析題目我們可以發(fā)現(xiàn)，這道題是要尋找最長的不含重復(fù)字符的子串，我們可以采取哈希表統(tǒng)計字符個數(shù)，滑動窗口控制子串長度的操作，分析一下可以知道，當right處于一個新位置就將其入窗口，若當前字符的出現(xiàn)次數(shù) > 1則表明當前字符串出現(xiàn)重復(fù)字符，此時讓left所在位置的元素出窗口，直到當前字符出現(xiàn)次數(shù) == 1，顯然，更新結(jié)果應(yīng)在出窗口后，代碼如下

class Solution

{

public:

int lengthOfLongestSubstring(string s)

{

int len = 0, n = s.size();

unordered_map hash;

for (int left = 0, right = 0; right < n; right++)

{

char in = s[right];

hash[in]++;

while (hash[in] > 1)

{

char out = s[left++];

hash[out]--;

}

len = max(len, right - left + 1);

}

return len;

}

};

2.?最大連續(xù)1的個數(shù)

題目鏈接：485. 最大連續(xù) 1 的個數(shù) - 力扣（LeetCode）

解析：分析題目我們可以發(fā)現(xiàn)，這道題是要尋找最長的只含有1的數(shù)組，我們可以直接滑動窗口統(tǒng)計長度的操作，分析一下可以知道，當right處于1的位置就將其入窗口，若right處于0的位置，則表明當前數(shù)組不是僅含有0的數(shù)組，此時讓left=right+1出窗口，顯然，更新結(jié)果應(yīng)在出窗口前，代碼如下

class Solution

{

public:

int findMaxConsecutiveOnes(vector& nums)

{

int len = 0, n = nums.size();

for (int left = 0, right = 0; right < n; right++)

{

if (nums[right] == 1) len = max(len, right - left + 1);

else left = right + 1;

}

return len;

}

};

3.?將x減到0的最小操作數(shù)

題目鏈接：1658. 將 x 減到 0 的最小操作數(shù) - 力扣（LeetCode）

解析：對于這道題分析后我們可以發(fā)現(xiàn)，正面解決可能比較困難，此時我們就可以采取正難則反的思想，這道題是要尋找將x減到0的最小操作數(shù)，換而言之，就是尋找值為sum-x的最長連續(xù)子區(qū)間，我們可以使用滑動窗口來尋找指定區(qū)間，分析一下可以知道，當right處于一個新位置就將其入窗口，若當前區(qū)間的總和?>= sum-x，則表明當前數(shù)組可能是一個合理區(qū)間，此時讓left所在位置的元素出窗口，直到當前區(qū)間總和 < sum-x，顯然，更新結(jié)果應(yīng)在出窗口前，代碼如下

class Solution

{

public:

int minOperations(vector& nums, int x)

{

int sum = 0, n = nums.size(), len = INT_MIN;

for (auto& e : nums) sum += e;

if (sum == x) return n;

int target = sum - x;

if (target < 0) return -1;

int v_sum = 0;

for (int left = 0, right = 0; right < n; right++)

{

v_sum += nums[right];

while (left < n && v_sum >= target)

{

if (v_sum == target) len = max(len, right - left + 1);

v_sum -= nums[left++];

}

}

return len == INT_MIN ? -1 : n - len;

}

};

4. 水果成籃

題目鏈接：904. 水果成籃 - 力扣（LeetCode）

解析：簡單翻譯一下這道題的題意就是僅能有2種樹被采摘，求最多能采摘多少樹，顯然我們可以使用滑動窗口 + 哈希表的解法，分析一下可以知道，當right處于一個新位置就將其入窗口，若當前哈希表中的種類數(shù)量 > 2，則表明當前這些樹超過了2個種類，此時讓left所在位置的元素出窗口，直到哈希表中的種類數(shù)量 ==?2，顯然，更新結(jié)果應(yīng)在出窗口后，代碼如下

class Solution

{

public:

int totalFruit(vector& fruits)

{

unordered_map hash;

int n = fruits.size();

int num = 0;

for (int left = 0, right = 0; right < n; right++)

{

int in = fruits[right];

hash[in]++;

while (hash.size() > 2)

{

int out = fruits[left++];

hash[out]--;

if (hash[out] == 0) hash.erase(out);

}

num = max(num, right - left + 1);

}

return num;

}

};

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

題目鏈接：438. 找到字符串中所有字母異位詞 - 力扣（LeetCode）

解析：對于這道題我們是要在s中找到所有p的異位詞，即需要遍歷一遍s，我們可以使用兩個哈希表，來分別統(tǒng)計s與p中對應(yīng)字符的個數(shù)，當right處于新位置時入窗口，當當前窗口大小size > p.size時，讓left所處位置出窗口，更新結(jié)果當然是在出窗口后，代碼如下

class Solution

{

public:

vector findAnagrams(string s, string p)

{

vector ret;

int hash1[26] = {0};

for (auto ch : p) hash1[ch-'a']++;

int hash2[26] = {0};

for (int left = 0, right = 0; right < s.size(); right++)

{

char in = s[right];

hash2[in - 'a']++;

if (right - left + 1 > p.size()) hash2[s[left++]-'a']--;

if (check(hash1, hash2)) ret.push_back(left);

}

return ret;

}

bool check(int* hash1, int* hash2)

{

for (int i = 0; i < 26; i++)

if (hash1[i] != hash2[i]) return false;

return true;

}

};

此外，我們可以對這個算法進行一個優(yōu)化——即使用變量count來統(tǒng)計有效字符數(shù)，即當一個right即將入窗口時，若hash2中它所對應(yīng)的字符 < hash1中它所對應(yīng)的字符時，count++，當一個left即將出窗口時，若hash2中它對應(yīng)的字符 <= hash1中它所對應(yīng)的字符時，count--，代碼如下

class Solution

{

public:

vector findAnagrams(string s, string p)

{

int count = 0;

vector ret;

int hash1[26] = {0};

for (auto ch : p) hash1[ch-'a']++;

int hash2[26] = {0};

for (int left = 0, right = 0; right < s.size(); right++)

{

char in = s[right];

if (hash2[in-'a'] < hash1[in-'a']) count++;

hash2[in-'a']++;

if (right - left + 1 > p.size())

{

char out = s[left++];

if (hash2[out - 'a'] <= hash1[out-'a']) count--;

hash2[out-'a']--;

}

if (count == p.size()) ret.push_back(left);

}

return ret;

}

};

6.?串聯(lián)所有單詞的子串

題目鏈接：30. 串聯(lián)所有單詞的子串 - 力扣（LeetCode）

解析：由于word中所有字符串長度相等，我們可以計算出word.lenth * word[i].lenth來計算出排列總數(shù)，然后再使用count計數(shù)的原理（詳見上題結(jié)尾），在一個right（這里的right代指一串子串）入窗口時，若hash2[right] < hash1[right]則count++，當窗口長度 >?word.lenth * word[i].lenth時，讓left出窗口，若hash2[left] <= hash1[left]則count--，結(jié)果在出窗口后更新，代碼如下

class Solution

{

public:

vector findSubstring(string s, vector& words)

{

int len = words.size() * words[0].size();

unordered_map hash1;

for (auto& s : words) hash1[s]++;

int n = s.size();

vector ret;

for (int i = 0; i < words[0].size(); i++)

{

unordered_map hash2;

int count = 0;

for (int left = i, right = i; right < n; right += words[0].size())

{

string in = s.substr(right, words[0].size());

// 使用hash1.count(in)可以避免創(chuàng)建新的映射關(guān)系，從而提高效率

if (hash1.count(in) && hash2[in] < hash1[in]) count++;

hash2[in]++;

if (right - left + 1 > len)

{

string out = s.substr(left, words[0].size());

if (hash2[out] <= hash1[out]) count--;

hash2[out]--;

left += words[0].size();

}

if (count == words.size()) ret.push_back(left);

}

}

return ret;

}

};

7. 最小覆蓋子串

題目鏈接：76. 最小覆蓋子串 - 力扣（LeetCode）

解析：分析這道題我們可以發(fā)現(xiàn)，這道題是要在s中尋找最小的子串使他能覆蓋t，我們可以使用滑動窗口來尋找指定區(qū)間，哈希表來統(tǒng)計對應(yīng)字符出現(xiàn)個數(shù)，分析一下可以知道，當right處于一個新位置就將其入窗口，若當區(qū)間有效字符種類數(shù)count==kind（t中字符種類個數(shù)），則表明當前子串屬于合理區(qū)間，此時讓left所在位置的元素出窗口，直到當前區(qū)間有效字符count < kind，顯然，更新結(jié)果應(yīng)在出窗口前，代碼如下

class Solution

{

public:

string minWindow(string s, string t)

{

if (s.size() < t.size()) return "";

int kind = 0;

int hash1[126] = {0};

for (auto ch : t) if (hash1[ch]++ == 0) kind++;

int hash2[126] = {0};

int len = 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++;

while (count == kind)

{

if (right - left + 1 < len)

{

len = right - left + 1;

begin = left;

}

char out = s[left++];

if (hash2[out] == hash1[out]) count--;

hash2[out]--;

}

}

if (begin == -1) return "";

else return s.substr(begin, len);

}

};

柚子快報激活碼778899分享：算法——滑動窗口

http://yzkb.51969.com/

精彩鏈接