前言

兄弟們，互聯網寒冬期，算法刷著走。上篇文章講了雙指針的左右指針，雙指針是數組類算法題中最重要的一個分支之一。這篇文章講雙指針技巧的滑動窗口。遇到雙指針的題目，直接套用模板就完事兒。另外，數組有下圖這些知識點與技巧。

思路

滑動窗口一般用于解決主串是否滿足子串的某些需求問題，比如，是否包含某個字串，是否含有字串的所有字符等。
滑動窗口有固定的解題模板。但是細節眾多，需要反復練習。

//s為原字符串，t為子字符串 public void slidingWindow(String s, String t) {//初始化窗口應該滿足的條件needMap，key=子串t中的字符，value=字符在t字符串中出現的次數Map<Character, Integer> needMap = new HashMap<>();for (int i = 0; i < t.length(); i++) {Character k = t.charAt(i);needMap.put(k, needMap.getOrDefault(k, 0) + 1);}//滑動窗口中包含的字符，及其數量，key=滑動窗口中的字符，value=字符出現的次數Map<Character, Integer> winMap = new HashMap<>();//l：窗口左指針，r窗口右指針，validCount：窗口中有多少個字符滿足了條件。int l = 0, r = 0, validCount = 0;while (r < s.length()) {//即將加入窗口的字符char in = s.charAt(r);//窗口右指針右移r++;//進行窗口內數據的操作...while (窗口是否應該收縮) {//即將從窗口移除的字符char out = s.charAt(l);//窗口左指針右移l++;//進行窗口內數據的操作...}} }

最小覆蓋子串

leetcode第76題

解題思路

套用滑動窗口模板。窗口左右指針下標從0開始遍歷原字符串。

窗口的右指針右移后，判斷加入窗口的字符是否是子串的字符，若是則更新winMap。更新后若winMap中該字符的value=needMap中該字符的value，說明滑動窗口中該字符數量與子串該字符的數量相等，則validCount+1。

當validCount=needMap.size()時，說明子串中的字符全部都包含在了滑動窗口中，且每個字符的字符數量也滿足。這時就把窗口的左指針右移，直到窗口中的字符串不在符合要求為止。

重復上訴步驟，找出最小的窗口。

復雜度分析

時間復雜度：O(nlogz+mlogz)，z是字符集的大小，n是原字符串的長度，m是子串長度。最壞情況下，窗口右指針會掃描一遍原數組，窗口左指針會掃描一邊原數組，所以最多掃描2n次，而每掃描一次，就有若干次的map.get與map.put，則復雜度是nlogz。初始化needMap時，需要掃描一遍子串，且也有map.get與map.put。則復雜度為O(nlogz + mlogz)。

空間復雜度：O(z)。因為需要建立兩個map分別存滑動窗口與字串中字符的出現次數，且每個map的鍵值對最多不會存放超過字符集的大小。

代碼

class Solution {public String minWindow(String s, String t) {Map<Character, Integer> needMap = new HashMap<>();for (int i = 0; i < t.length(); i++) {Character k = t.charAt(i);needMap.put(k, needMap.getOrDefault(k, 0) + 1);}Map<Character, Integer> winMap = new HashMap<>();int l = 0, r = 0, validCount = 0, start = 0, minWin = Integer.MAX_VALUE;while (r < s.length()) {char in = s.charAt(r);r++;if (needMap.containsKey(in)) {winMap.put(in, winMap.getOrDefault(in, 0) + 1);//窗口中該字符的數量等于字串中該字符的數量if (winMap.get(in).equals(needMap.get(in))) {validCount++;}}//窗口中所有字符的數量都大于等于字串中字符的相應數量，說明這是一個滿足題意的子串while (validCount == needMap.size()) {//記錄滿足條件時的最小窗口if (r - l < minWin) {start = l;minWin = r - l;}char out = s.charAt(l);l++;if (needMap.containsKey(out)) {winMap.put(out, winMap.getOrDefault(out, 0) - 1);//當窗口中該字符的數量小于了字串中的數量if (winMap.get(out) < needMap.get(out)) {validCount--;}}}}return Integer.MAX_VALUE == minWin ? "" : s.substring(start, start + minWin);} }

字符串的排列

leetcode第567題

解題思路

套用滑動窗口模板。窗口左右指針下標從0開始去遍歷s2。

窗口的右指針右移后，判斷加入窗口的字符是否是s1的字符，若是則更新winMap。更新后若winMap中該字符的value=needMap中該字符的value，說明滑動窗口中該字符數量與s1中的該字符的數量相等，則validCount+1。

當validCount=needMap.size()時，說明s1中的字符全部都包含在了滑動窗口中。此時進行判斷，當窗口的長度=s1的長度時，說明是一個合法序列，則返回true。

重復上訴步驟，若遍歷結束后都沒找到合法序列，則返回false。

復雜度分析

時間復雜度：O(nlogz + mlogz)，z是字符集的大小。n 是s1字符串的長度，m是s2字串長度。最壞情況下，窗口右指針會掃描一遍s2，窗口左指針會掃描一遍s2，所以最多掃描2m次，而每掃描一次，就用若干次的map.get與map.put，則復雜度是mlogz。初始化needMap時，需要掃描一遍s1，每次掃描也有map.get與map.put。則復雜度為O(nlogz + mlogz)。

空間復雜度：O(z)。因為需要建立兩個map分別存滑動窗口與字串中字符的出現次數，且每個map的鍵值對最多不會存放超過字符集的大小。

代碼

class Solution {public boolean checkInclusion(String s1, String s2) {Map<Character, Integer> needMap = new HashMap<>();for (int i = 0; i < s1.length(); i++) {Character k = s1.charAt(i);needMap.put(k, needMap.getOrDefault(k, 0) + 1);}Map<Character, Integer> winMap = new HashMap<>();int l = 0, r = 0, validCount = 0;while (r < s2.length()) {char in = s2.charAt(r);r++;if (needMap.containsKey(in)) {winMap.put(in, winMap.getOrDefault(in, 0) + 1);if (winMap.get(in).equals(needMap.get(in))) {validCount++;}}while (validCount == needMap.size()) {if (r - l == s1.length()) {return true;}char out = s2.charAt(l);l++;if (needMap.containsKey(out)) {winMap.put(out, winMap.getOrDefault(out, 0) - 1);if (winMap.get(out) < needMap.get(out)) {validCount--;}}}}return false;} }

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

leetcode第438題

解題思路

套用滑動窗口模板。窗口左右指針下標從0開始去遍歷s。

窗口的右指針右移后，判斷加入窗口的字符是否是p的字符，若是則更新winMap。更新后若winMap中該字符的value=needMap中該字符的value，說明滑動窗口中該字符數量與p中的該字符的數量相等，則validCount+1。

當validCount=needMap.size()時，說明p中的字符全部都包含在了滑動窗口中。此時進行判斷，當窗口的長度=s的長度時，說明是一個合法序列，則加入列表中。

重復上訴步驟，找出所有的合法序列。

復雜度分析

時間復雜度：O(nlogz + mlogz)，n是s字符串的長度，m是p字串長度。最壞情況下，窗口右指針會掃描一遍s，窗口左指針會掃描一遍s，所以最多掃描2n次，而每掃描一次，就用若干次的map.get與map.put，則復雜度是nlogz。初始化needMap時，需要掃描一遍p，每次掃描也有map.get與map.put。則復雜度為O(nlogz + mlogz)。

空間復雜度：O(z)。z是字符集的大小。因為需要建立兩個map分別存滑動窗口與字串中字符的出現次數，且每個map的鍵值對最多不會存放超過字符集大小。

代碼

class Solution {public List<Integer> findAnagrams(String s, String p) {Map<Character, Integer> needMap = new HashMap<>();for (int i = 0; i < p.length(); i++) {Character k = p.charAt(i);needMap.put(k, needMap.getOrDefault(k, 0) + 1);}Map<Character, Integer> winMap = new HashMap<>();List<Integer> list = new ArrayList<>();int l = 0, r = 0, validCount = 0;while (r < s.length()) {char in = s.charAt(r);r++;if (needMap.containsKey(in)) {winMap.put(in, winMap.getOrDefault(in, 0) + 1);if (winMap.get(in).equals(needMap.get(in))) {validCount++;}}while (validCount == needMap.size()) {if (r - l == p.length()) {list.add(l);}char out = s.charAt(l);l++;if (needMap.containsKey(out)) {winMap.put(out, winMap.get(out) - 1);if (winMap.get(out) < needMap.get(out)) {validCount--;}}}}return list;} }

無重復字符的最長子串

leetcode第3題

解題思路

此題不能用常規的滑動窗口模板。由于沒有子串，所以不需要needMap去統計子串的字符，也不需要validCount統計窗口內滿足子串相關條件的字符數。

窗口左右指針下標從0開始去遍歷s。窗口的右指針右移后，將加入窗口的字符更新進winMap。

當winMap中剛加入窗口的字符的value大于1，則說明窗口中有重復的字符了。開始右移左指針，并實時更新winMap，直到winMap中剛加入窗口的字符的value不大于1。此時窗口長度就是一個無重復的子串長度。

重復上訴步驟，找出最大子串長度。

復雜度分析

時間復雜度：O(nlogz)，n 是s字符串的長度。最壞情況下，窗口右指針會掃描一遍s，窗口左指針會掃描一遍s，所以最多掃描2n次。而每掃描一次，就用若干次的map.get與map.put，則復雜度為O(nlogz)。

空間復雜度：O(z)。z是字符集的大小。因為需要建立一個map存滑動窗口中字符的出現次數，且map的鍵值對最多不會存放超過z是字符集的大小。

代碼

class Solution {public int lengthOfLongestSubstring(String s) {Map<Character, Integer> winMap = new HashMap<>();int l = 0, r = 0, max = Integer.MIN_VALUE;while (r < s.length()) {char in = s.charAt(r);r++;winMap.put(in, winMap.getOrDefault(in, 0) + 1);while (winMap.get(in) > 1) {char out = s.charAt(l);l++;winMap.put(out, winMap.get(out) - 1);}max = Math.max(r - l, max);}return max == Integer.MIN_VALUE ? 0 : max;} }

結尾

滑動窗口套路固定，遇到類型題時，直接模板默寫代碼，屢試不爽。 下篇文章講二分搜索。

感謝各位人才的點贊、收藏和評論，干貨文章持續更新中，下篇文章再見！

總結

以上是生活随笔為你收集整理的数组-滑动窗口（直接套模板完事儿）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。