大家好，我是小浩。今天是小浩算法 “365刷題計(jì)劃” 滑動(dòng)窗口系列 - 整合篇。之前給大家講解過一些滑動(dòng)窗口的題目，但未作系統(tǒng)整理。

所以我就出了這個(gè)整合合集，整合工作中除了保留原有滑動(dòng)窗口系列的題目，也加入了一些新的內(nèi)容。希望大家轉(zhuǎn)發(fā)支持！

• TCP滑動(dòng)窗口

• 滑動(dòng)窗口最大值

• 滑動(dòng)窗口的模式

• 無重復(fù)字符的最長子串

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

01PART從TCP滑動(dòng)窗口講起

滑動(dòng)窗口協(xié)議(Sliding Window Protocol)，屬于TCP協(xié)議的一種應(yīng)用，用于網(wǎng)絡(luò)數(shù)據(jù)傳輸時(shí)的流量控制，以避免擁塞的發(fā)生。該協(xié)議允許發(fā)送方在停止并等待確認(rèn)前發(fā)送多個(gè)數(shù)據(jù)分組。由于發(fā)送方不必每發(fā)一個(gè)分組就停下來等待確認(rèn)，因此該協(xié)議可以加速數(shù)據(jù)的傳輸，提高網(wǎng)絡(luò)吞吐量。

大多數(shù)人接觸滑動(dòng)窗口應(yīng)該是在TCP協(xié)議中，當(dāng)我們從一個(gè)機(jī)器向另一個(gè)機(jī)器傳輸數(shù)據(jù)時(shí)，并不能一下子就傳給對方。而是操作系統(tǒng)將這些數(shù)據(jù)變成連續(xù)的數(shù)據(jù)包，然后一部分一部分的傳給對方。因?yàn)榫W(wǎng)絡(luò)就好像一個(gè)沙漏，中間的連接管會(huì)決定網(wǎng)絡(luò)傳輸?shù)恼鎸?shí)速度！

如果數(shù)據(jù)一口氣發(fā)送給對方，說小點(diǎn)就是網(wǎng)絡(luò)壓力過大丟包重試，說大點(diǎn)沒準(zhǔn)就直接導(dǎo)致網(wǎng)絡(luò)崩潰。那這里和滑動(dòng)窗口有什么關(guān)系呢？當(dāng)這些數(shù)據(jù)包一批一批的發(fā)送給對方的時(shí)候，其內(nèi)部實(shí)質(zhì)就是通過一個(gè)滑動(dòng)窗口來維護(hù)數(shù)據(jù)。

下面兩張圖畫的挺好，我就不造輪子了：

那為什么TCP這里要用滑動(dòng)窗口來實(shí)現(xiàn)數(shù)據(jù)傳輸呢？因?yàn)槲也皇菍ｉT講TCP的滑動(dòng)窗口，所以我就簡單說下：滑動(dòng)窗口的大小可以依據(jù)策略動(dòng)態(tài)調(diào)整，應(yīng)用可根據(jù)自身的處理能力來控制窗口的大小，實(shí)現(xiàn)流量限制等功能。

(大概就是這么個(gè)玩意)

上面的知識(shí)，聽懂了也好，沒聽懂也罷。至少到這里你需要知道兩件事：

• 滑動(dòng)窗口這玩意，并不是說面試的時(shí)候考考，真實(shí)場景也會(huì)用到！很重要！

• 滑動(dòng)窗口的核心，說白了就丫一成語，張弛有度。(動(dòng)態(tài)調(diào)整，容易擴(kuò)展，可長可短，巴拉巴拉.....)

那我們算法里的滑動(dòng)窗口，其實(shí)也是一碼事。常用來處理一些連續(xù)問題。不管是固定窗口大小的，還是非固定窗口大小的(可變窗口)，統(tǒng)統(tǒng)都屬于滑動(dòng)窗口類型的題目！下面我將通過幾道經(jīng)典例題，為大家講解。

02PART滑動(dòng)窗口最大值

先上一道難度比較高的題目！

第239題：給定一個(gè)數(shù)組 nums，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口內(nèi)的 k 個(gè)數(shù)字。滑動(dòng)窗口每次只向右移動(dòng)一位。返回滑動(dòng)窗口中的最大值。

給定一個(gè)數(shù)組 nums，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口內(nèi)的 k 個(gè)數(shù)字。滑動(dòng)窗口每次只向右移動(dòng)一位。

返回滑動(dòng)窗口中的最大值所構(gòu)成的數(shù)組。

示例:

輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3

輸出: [3,3,5,5,6,7]?

解釋:?

? 滑動(dòng)窗口的位置? ? ? ? ? ? ? ? 最大值

---------------? ? ? ? ? ? ? ?-----

[1? 3? -1] -3? 5? 3? 6? 7? ? ? ?3

?1 [3? -1? -3] 5? 3? 6? 7? ? ? ?3

?1? 3 [-1? -3? 5] 3? 6? 7? ? ? ?5

?1? 3? -1 [-3? 5? 3] 6? 7? ? ? ?5

?1? 3? -1? -3 [5? 3? 6] 7? ? ? ?6

?1? 3? -1? -3? 5 [3? 6? 7]? ? ? 7

本題對于題目沒有太多需要額外說明的，應(yīng)該都能理解，直接進(jìn)行分析。我們很容易想到，可以通過遍歷所有的滑動(dòng)窗口，找到每一個(gè)窗口的最大值，來進(jìn)行暴力求解。那一共有多少個(gè)滑動(dòng)窗口呢，小學(xué)題目，可以得到共有 L-k+1 個(gè)窗口。

假設(shè)?nums = [1,3,-1,-3,5,3,6,7]，和 k = 3，窗口數(shù)為 6

根據(jù)分析，直接完成代碼：

1//java
2class?Solution?{
3????public?int[]?maxSlidingWindow(int[]?nums,?int?k)?{
4????????int?len?=?nums.length;
5????????if?(len?*?k?==?0)?return?new?int[0];
6????????int?[]?win?=?new?int[len?-?k?+?1];
7????????//遍歷所有的滑動(dòng)窗口
8????????for?(int?i?=?0;?i?1;?i++)?{
9????????????int?max?=?Integer.MIN_VALUE;
10????????????//找到每一個(gè)滑動(dòng)窗口的最大值
11????????????for(int?j?=?i;?j?12????????????????max?=?Math.max(max,?nums[j]);
13????????????}
14????????????win[i]?=?max;
15????????}
16????????return?win;
17????}
18}

It's Bullshit！結(jié)果令我們很不滿意，時(shí)間復(fù)雜度達(dá)到了O(LK)，如果面試問到這道題，基本上只寫出這樣的代碼，一定就掛掉了。那我們怎么樣優(yōu)化時(shí)間復(fù)雜度呢？有沒有可以O(shè)(L)的實(shí)現(xiàn)呢？=_=

這里不賣關(guān)子，其實(shí)這道題比較經(jīng)典，我們可以采用隊(duì)列，DP，堆等方式進(jìn)行求解，所有思路的主要源頭應(yīng)該都是在窗口滑動(dòng)的過程中，如何更快的完成查找最大值的過程。但是最典型的解法還是使用雙端隊(duì)列。具體怎么來求解，一起看一下。

首先，我們了解一下，什么是雙端隊(duì)列：是一種具有隊(duì)列和棧的性質(zhì)的數(shù)據(jù)結(jié)構(gòu)。雙端隊(duì)列中的元素可以從兩端彈出或者插入。

我們可以利用雙端隊(duì)列來實(shí)現(xiàn)一個(gè)窗口，目的是讓該窗口可以做到張弛有度(漢語博大精深，也就是長度動(dòng)態(tài)變化。其實(shí)用游標(biāo)或者其他解法的目的都是一樣的，就是去維護(hù)一個(gè)可變長的窗口)

然后我們再做一件事，只要遍歷該數(shù)組，同時(shí)在雙端隊(duì)列的頭去維護(hù)當(dāng)前窗口的最大值(在遍歷過程中，發(fā)現(xiàn)當(dāng)前元素比隊(duì)列中的元素大，就將原來隊(duì)列中的元素祭天)，在整個(gè)遍歷的過程中我們再記錄下每一個(gè)窗口的最大值到結(jié)果數(shù)組中。最終結(jié)果數(shù)組就是我們想要的，整體圖解如下。

假設(shè)?nums = [1,3,-1,-3,5,3,6,7]，和 k = 3

(個(gè)人認(rèn)為我畫的這個(gè)圖是目前全網(wǎng)對于雙端隊(duì)列本題解法比較清晰的一個(gè)...所以我覺得如果不點(diǎn)個(gè)贊的話...晤..)

根據(jù)分析，得出代碼：

1//go
2func?maxSlidingWindow(nums?[]int,?k?int)?[]int?{
3????if?len(nums)?==?0?{
4????????return?[]int{}
5????}
6????//用切片模擬一個(gè)雙端隊(duì)列
7????queue?:=?[]int{}
8????result?:=?[]int{}
9????for?i?:=?range?nums?{
10????????for?i?>?0?&&?(len(queue)?>?0)?&&?nums[i]?>?queue[len(queue)-1]?{
11????????????//將比當(dāng)前元素小的元素祭天
12????????????queue?=?queue[:len(queue)-1]
13????????}
14????????//將當(dāng)前元素放入queue中
15????????queue?=?append(queue,?nums[i])
16????????if?i?>=?k?&&?nums[i-k]?==?queue[0]?{
17????????????//維護(hù)隊(duì)列，保證其頭元素為當(dāng)前窗口最大值
18????????????queue?=?queue[1:]
19????????}
20????????if?i?>=?k-1?{
21????????????//放入結(jié)果數(shù)組
22????????????result?=?append(result,?queue[0])
23????????}
24????}
25????return?result
26}

Perfact，題目完成！看著一下子超越百分之99的用戶，是不是感覺很爽呢？

03PART滑動(dòng)窗口的模式

滑動(dòng)窗口的題目其實(shí)是一定模式的。對于大部分滑動(dòng)窗口類型的題目，一般是考察字符串的匹配。比較標(biāo)準(zhǔn)的題目，會(huì)給出一個(gè)模式串B，以及一個(gè)目標(biāo)串A。然后提出問題，找到A中符合對B一些限定規(guī)則的子串或者對A一些限定規(guī)則的結(jié)果，最終再將搜索出的子串完成題意中要求的組合或者其他。

比如：給定一個(gè)字符串 s 和一個(gè)非空字符串 p，找到 s 中所有是 p 的字母異位詞的子串，返回這些子串的起始索引。

又或者：給你一個(gè)字符串 S、一個(gè)字符串 T，請?jiān)谧址?S 里面找出：包含 T 所有字母的最小子串。

再如：給定一個(gè)字符串 s 和一些長度相同的單詞 words。找出 s 中恰好可以由 words 中所有單詞串聯(lián)形成的子串的起始位置。

都是屬于這一類的標(biāo)準(zhǔn)題型。而對于這一類題目，我們常用的解題思路，是去維護(hù)一個(gè)可變長度的滑動(dòng)窗口。無論是使用雙指針，還是使用雙端隊(duì)列，又或者用游標(biāo)等其他奇技淫巧，目的都是一樣的。? ?

04PART無重復(fù)字符的最長子串

在上文中，我們使用雙端隊(duì)列完成了滑動(dòng)窗口的一道頗為困難的題目，以此展示了什么是滑動(dòng)窗口。在本節(jié)中我們將繼續(xù)深入分析，探索滑動(dòng)窗口題型一些具有模式性的解法。

第3題：給定一個(gè)字符串，請你找出其中不含有重復(fù)字符的 最長子串 的長度。

示例 1:

輸入: "abcabcbb"

輸出: 3?

解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"，所以其長度為 3。

示例 2:

輸入: "bbbbb"

輸出: 1

解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "b"，所以其長度為 1。

示例 3:

輸入: "pwwkew"

輸出: 3

解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "wke"，所以其長度為 3。

請注意，你的答案必須是 子串 的長度，"pwke" 是一個(gè)子序列，不是子串。

直接分析題目，假設(shè)我們的輸入為“abcabcbb”，我們只需要維護(hù)一個(gè)窗口在輸入字符串中進(jìn)行移動(dòng)。如下圖：

當(dāng)下一個(gè)元素在窗口沒有出現(xiàn)過時(shí)，我們擴(kuò)大窗口。

當(dāng)下一個(gè)元素在窗口中出現(xiàn)過時(shí)，我們縮小窗口，將出現(xiàn)過的元素以及其左邊的元素統(tǒng)統(tǒng)移出：

在整個(gè)過程中，我們記錄下窗口出現(xiàn)過的最大值即可。而我們唯一要做的，只需要盡可能擴(kuò)大窗口。

那我們代碼中通過什么來維護(hù)這樣的一個(gè)窗口呢？anyway~ 不管是隊(duì)列，雙指針，甚至通過map來做，都可以。

我們演示一個(gè)雙指針的做法：

1//java
2public?class?Solution?{
3????public?static?int?lengthOfLongestSubstring(String?s)?{
4????????int?n?=?s.length();
5????????Set?set?=?new?HashSet<>(); 6????????int?result?=?0,?left?=?0,?right?=?0; 7????????while?(left? 8????????????//charAt：返回指定位置處的字符 9????????????if?(!set.contains(s.charAt(right)))?{10????????????????set.add(s.charAt(right));11????????????????right++;12????????????????result?=?Math.max(result,?right?-?left);13????????????}?else?{14????????????????set.remove(s.charAt(left));15????????????????left++;16????????????}17????????}18????????return?result;19????}20}

通過觀察，我們能看出來。如果是最壞情況的話，我們每一個(gè)字符都可能會(huì)訪問兩次，left一次，right一次，時(shí)間復(fù)雜度達(dá)到了O(2N)，這是不可饒恕的。不理解的話看下圖：

假設(shè)我們的字符串為“abcdc”，對于abc我們都訪問了2次。

那如何來進(jìn)一步優(yōu)化呢？

其實(shí)我們可以定義字符到索引的映射，而不是簡單通過一個(gè)集合來判斷字符是否存在。這樣的話，當(dāng)我們找到重復(fù)的字符時(shí)，我們可以立即跳過該窗口，而不需要對之前的元素進(jìn)行再次訪問。

1//java
2public?class?Solution?{
3????public?static?int?lengthOfLongestSubstring(String?s)?{
4????????int?n?=?s.length(),?result?=?0;
5????????Map?map?=?new?HashMap<>();? 6????????for?(int?right?=?0,?left?=?0;?right? 7????????????if?(map.containsKey(s.charAt(right)))?{ 8????????????????left?=?Math.max(map.get(s.charAt(right)),?left); 9????????????}10????????????result?=?Math.max(result,?right?-?left?+?1);11????????????map.put(s.charAt(right),?right?+?1);12????????}13????????return?result;14????}15}

修改之后，我們發(fā)現(xiàn)雖然時(shí)間復(fù)雜度有了一定提高，但是還是比較慢！如何更進(jìn)一步的優(yōu)化呢？我們可以使用一個(gè)256位的數(shù)組來替代hashmap，以進(jìn)行優(yōu)化。(因?yàn)锳SCII碼表里的字符總共有128個(gè)。ASCII碼的長度是一個(gè)字節(jié)，8位，理論上可以表示256個(gè)字符，但是許多時(shí)候只談128個(gè)。具體原因可以下去自行學(xué)習(xí)~)

1//java
2class?Solution?{
3????public?int?lengthOfLongestSubstring(String?s)?{
4????????int?len?=?s.length();
5????????int?result?=?0;
6????????int[]?charIndex?=?new?int[256];
7????????for?(int?left?=?0,?right?=?0;?right? 8????????????char?c?=?s.charAt(right);
9????????????left?=?Math.max(charIndex[c],?left);
10????????????result?=?Math.max(result,?right?-?left?+?1);
11????????????charIndex[c]?=?right?+?1;
12????????}
13????????return?result;
14????}
15}

我們發(fā)現(xiàn)優(yōu)化后時(shí)間復(fù)雜度有了極大的改善！這里簡單說一下原因，對于數(shù)組和hashmap訪問時(shí)，兩個(gè)誰快誰慢不是一定的，需要思考hashmap的底層實(shí)現(xiàn)，以及數(shù)據(jù)量大小。但是在這里，因?yàn)橐阎舜L問數(shù)據(jù)的下標(biāo)，可以直接尋址，所以極大的縮短了查詢時(shí)間。

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

如果完成上面兩道題的學(xué)習(xí)，相信大家對滑動(dòng)窗口已不陌生。下面繼續(xù)完成一道題目，來進(jìn)行鞏固學(xué)習(xí)。

第438題：給定一個(gè)字符串 s 和一個(gè)非空字符串 p，找到 s 中所有是 p 的字母異位詞的子串，返回這些子串的起始索引。

字符串只包含小寫英文字母，并且字符串 s 和 p 的長度都不超過 20100。

說明：

字母異位詞指字母相同，但排列不同的字符串。

不考慮答案輸出的順序。

示例 1:

輸入:

s: "cbaebabacd" p: "abc"

輸出:

[0, 6]

解釋:

起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母異位詞。

起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母異位詞。

示例 2:

輸入:

s: "abab" p: "ab"

輸出:

[0, 1, 2]

解釋:

起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母異位詞。

起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母異位詞。

起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母異位詞。

直接套用之前的模式，使用雙指針來模擬一個(gè)滑動(dòng)窗口進(jìn)行解題。分析過程如下：

假設(shè)我們有字符串為“cbaebabacd”，目標(biāo)串為“abc”

我們通過雙指針維護(hù)一個(gè)窗口，由于我們只需要判斷字母異位詞，我們可以將窗口初始化大小和目標(biāo)串保持一致。(當(dāng)然，你也可以初始化窗口為1，逐步擴(kuò)大)

而判斷字母異位詞，我們需要保證窗口中的字母出現(xiàn)次數(shù)與目標(biāo)串中的字母出現(xiàn)次數(shù)一致。這里因?yàn)樽帜钢挥?6個(gè)，直接使用數(shù)組來替代map進(jìn)行存儲(chǔ)(和上一講中的ASCII使用256數(shù)組存儲(chǔ)思想一致)。

pArr為目標(biāo)串?dāng)?shù)組，sArr為窗口數(shù)組。我們發(fā)現(xiàn)初始化數(shù)組，本身就滿足，記錄下來。(這里圖示用map模擬數(shù)組，便于理解)

然后我們通過移動(dòng)窗口，來更新窗口數(shù)組，進(jìn)而和目標(biāo)數(shù)組匹配，匹配成功進(jìn)行記錄。每一次窗口移動(dòng)，左指針前移，原來左指針位置處的數(shù)值減1，表示字母移出；同時(shí)右指針前移，右指針位置處的數(shù)值加1，表示字母移入。詳細(xì)過程如下：

最終，當(dāng)右指針到達(dá)邊界，意味著匹配完成。然后我們根據(jù)分析，給出代碼(整個(gè)題解都是套用之前的解題套路。)

class?Solution?{

????public?List?findAnagrams(String?s,?String?p)?{

????????if?(s?==?null?||?p?==?null?||?s.length()?return?new?ArrayList<>();

????????List?list?=?new?ArrayList<>();int[]?pArr?=?new?int[26];int[]?sArr?=?new?int[26];for?(int?i?=?0;?i?????????????sArr[s.charAt(i)?-?'a']++;??
????????????pArr[p.charAt(i)?-?'a']++;
????????}for?(int?i?=?0;?i?????????????int?index?=?p.charAt(i)?-?'a';
????????}int?i?=?0;int?j?=?p.length();//?窗口大小固定為p的長度while?(j?????????????if?(isSame(pArr,?sArr))
????????????????list.add(i);????????????//sArr[s.charAt(i)?-?'a']--?左指針位置處字母減1
????????????sArr[s.charAt(i)?-?'a']--;
????????????i++;//sArr[s.charAt(j)?-?'a']++?右指針位置處字母加1
????????????sArr[s.charAt(j)?-?'a']++;
????????????j++;
????????}if?(isSame(?pArr,?sArr))
????????????list.add(i);return?list;
????}public?boolean?isSame(int[]?arr1,?int[]?arr2)?{for?(int?i?=?0;?i?????????????if?(arr1[i]?!=?arr2[i])return?false;return?true;
????}
}

當(dāng)然，這種解法并不是最優(yōu)解！大家有興趣的話，可以下去自行再研究一下如何在該解法的基礎(chǔ)上再進(jìn)行優(yōu)化。

06PART啰嗦一下

關(guān)于滑動(dòng)窗口的整合篇到這里就完事了，大家應(yīng)該可以發(fā)現(xiàn)，不管我們是使用雙指針，又或是雙端隊(duì)列來完成滑動(dòng)窗口的題目，核心思想都是差不多的。

寫原創(chuàng)文章不容易，尤其是算法類文章。但我后面還是會(huì)繼續(xù)堅(jiān)持輸出更多優(yōu)質(zhì)的內(nèi)容。感謝大家一直以來的支持！如果覺得還不錯(cuò)的話，幫我轉(zhuǎn)發(fā)一下！感謝！

80道漫畫圖解算法題匯總(0406版本)

動(dòng)態(tài)規(guī)劃入門看這篇就夠了，萬字長文！

如果你問我對學(xué)習(xí)算法有什么建議，可以看：

漫畫：小白為了面試如何刷題？(嘔心瀝血算法指導(dǎo)篇)

漫畫：嘔心泣血算法指導(dǎo)篇(真正的干貨，怒懟那些說算法沒用的人)

?小浩算法，每日一題

關(guān)注領(lǐng)取《圖解算法》高清版

進(jìn)群的小伙伴請加右側(cè)私人微信(備注：進(jìn)群)

總結(jié)

以上是生活随笔為你收集整理的uiautomation遍历windows所有窗口_万字长文！滑动窗口看这篇就够了！的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。