柚子快報激活碼778899分享：初識算法 · 滑動窗口(1)
目錄
?前言：
長度最小的子數(shù)組
題目解析
算法原理
算法編寫
無重復(fù)長度的最小字符串
題目解析
算法原理
算法編寫
?前言：
本文開始，介紹的是滑動窗口算法類型的題目，滑動窗口本質(zhì)上其實(shí)也是雙指針，但是呢，前文介紹的雙指針是二者相向移動的：
滑動窗口就是同向移動的：
本文通過2個題目，介紹滑動窗口的基本使用，介紹的題目分別是：
209. 長度最小的子數(shù)組 - 力扣（LeetCode）
3. 無重復(fù)字符的最長子串 - 力扣（LeetCode）
通過三個步驟介紹，第一步是題目解析，第二步是算法原理，第三步是算法編寫，同樣的，會在題目解析部分看是否存在暴力解法，那么話不多說，進(jìn)入第一道題目。
長度最小的子數(shù)組
題目解析
題目的要求是，找到一段連續(xù)的區(qū)間，使得該區(qū)間的值的總和大于等于target，如果有這種類型的區(qū)間，返回值應(yīng)該是這些區(qū)間的最小長度。如果沒有這種子數(shù)組，返回的應(yīng)該為0。
然后是兩個示例。那么對于這道題我們可不可以暴力解法呢？當(dāng)然是可以的。
我們只需要找到所有滿足該條件的區(qū)間，并判斷他們的長度即可，但是時間復(fù)雜度的話，O(N^2)是肯定的了，并且在這道題目上是會超時的，所以有興趣的同學(xué)們可以自行嘗試。
那么為什么該題目一看就可以使用滑動窗口呢？
因?yàn)橐蟮氖且欢芜B續(xù)的空間，作為經(jīng)驗(yàn)，碰到要求是連續(xù)空間的題目，我們不妨往滑動窗口上靠一下。
現(xiàn)在就進(jìn)入算法原理部分。
算法原理
滑動窗口的本質(zhì)是，兩個指針同向移動，我們通過這兩個指針的移動，判斷區(qū)間之和是否滿足，如果滿足就進(jìn)行比較長度大小。
那么如果使用滑動窗口呢？ 最開始兩個指針的起點(diǎn)應(yīng)該是一樣的，如果兩個指針的位置不是一樣的，就會導(dǎo)致我們需要多加一個循環(huán)來專門求這個區(qū)間的和，所以現(xiàn)在：
int left = 0, right = 0;
這是肯定的，那么滑動窗口，我們可以記住兩個名詞，一個是進(jìn)窗口，一個是出窗口，什么時候進(jìn)窗口，什么是出窗口，是我們題目所關(guān)心的。
進(jìn)窗口代表，區(qū)間之和 出窗口代表，區(qū)間之和>target，出窗口判斷里面存在的最小長度即可。 基本的原理就是如此，一進(jìn)一出之間，可以將題目解決成功。 算法編寫 class Solution { public: int minSubArrayLen(int target, vector { int ans = INT_MAX, left = 0, right = 0 ,sum = 0; for(;right < nums.size();right++) { sum += nums[right]; while(sum >= target) { ans = min(ans,right - left + 1);//如果ans為0 那么這一步永遠(yuǎn)都是0 sum -= nums[left++]; } } return ans == INT_MAX ? 0 : ans; } }; 但是這道題目有個惡心的點(diǎn)在于，如果最開始的長度不定義為很大的一個數(shù)，判斷比較的時候，通過min是得不到最小的數(shù)的，所以我們應(yīng)該將ans定義為INT_MAX，只要是很大的數(shù)就可以。 至此，題目就解析完畢了。 無重復(fù)長度的最小字符串 題目解析 題目非常簡短，通過條件就是返回不含重復(fù)字符的最長字串的長度，那么對于字符來說，題目中給的要求是： 所以我們?yōu)榱伺袛嘤袥]有重復(fù)，我們需要一種方法來判斷是否存在某種映射，我們在這里不妨使用哈希映射，使用數(shù)組模仿哈希表，那么首當(dāng)其沖的，我們不妨判斷一下該題目是否存在暴力解法。 那肯定是存在的，我們使用兩個for循環(huán)，第二個循環(huán)找最末尾的元素，同時判斷映射值是否大于1，大于1直接返回即可。時間復(fù)雜度肯定是O(N^2)，是可以通過的。 但是鑒于這道題的本質(zhì)是一段區(qū)間，所以我們不妨使用滑動窗口解答。 算法原理 上一道題目的滑動窗口是長度最小的子數(shù)組，判斷條件是大于等于>=target，這道題的判斷條件是hash映射是否大于1，所以，得出一個結(jié)論是：使用滑動窗口的題目，有三部曲，第一是進(jìn)窗口，第二是判斷，第三是出窗口。 后面的題目都是很死板的使用該步驟。 那么我們判斷的方法同樣是使用哈希映射，判斷映射如果大于1就出，出完了記錄對應(yīng)的ans，或者是映射滿足條件，也記錄對應(yīng)的ans即可。 最后返回ans就行。 算法編寫 class Solution { public: int lengthOfLongestSubstring(string s) { int hash[256] = { 0 }, ans = 0; for(int left = 0, right = 0;right < s.size();right++) { hash[s[right]]++; while(hash[s[right]] > 1) { hash[s[left++]]--; } ans = max(ans,right - left + 1); } return ans; } }; 滑動窗口的開篇就結(jié)束咯~ 感謝閱讀！ 柚子快報激活碼778899分享：初識算法 · 滑動窗口(1) 參考文章
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場。
轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。
Vevor工具商城
