Leetcode 必備算法：聊聊滑動窗口
前言
我們刷leetcode的時候，經(jīng)常會遇到滑動窗口類型題目?；瑒哟翱趩栴}非常經(jīng)典，也很有技巧性，一般大廠也喜歡問。今天跟大家一起來學習滑動窗口的套路，文章如果有不正確的地方，歡迎大家指出哈，感謝感謝~
- 什么是滑動窗口?
- 一道算法題走進滑動窗口
- 滑動窗口可以用來解決哪些問題?
- 滑動窗口框架套路
- leetcode案例分析
什么是滑動窗口
滑動窗口這個詞，相信大家耳熟能詳啦。因為說到TCP的時候，經(jīng)常談起滑動窗口協(xié)議(Sliding Window Protocol),它是TCP協(xié)議的一種應(yīng)用，用于網(wǎng)絡(luò)數(shù)據(jù)傳輸時的流量控制，以避免擁塞的發(fā)生。
TCP頭部有個字段叫win，也即那個16位的窗口大小，它告訴對方本端的TCP接收緩沖區(qū)還能容納多少字節(jié)的數(shù)據(jù)，這樣對方就可以控制發(fā)送數(shù)據(jù)的速度，從而達到流量控制的目的。
TCP的滑動窗口在某一個時刻就是固定窗口大小的滑動窗口，隨著網(wǎng)絡(luò)流量等因素改變窗口大小也會隨著改變。算法中的滑動窗口有點類似，就是維護一個窗口(隊列/數(shù)組)，不斷滑動，然后更新答案?；瑒哟翱?，指的是這樣一類問題的求解方法，在數(shù)組上通過雙指針同向移動而解決的一類問題。
一個例子走進滑動窗口算法
我們來看一道算法題吧：給定一個整數(shù)數(shù)組，計算長度為k的連續(xù)子數(shù)組的最大總和。
- 輸入：arr [] = {100,200,300,400} k = 2
- 輸出：700
- 解釋：300 + 400 = 700
看到這個題目，我們馬上想到暴力法去解決了，兩個for搞定：
- public int maxSum(int[] arry, int k) {
- int size = arry.length;
- int maxSum = 0;
- for (int i = 0; i < size - k + 1; i++) {
- int currentSum = 0;
- for (int j = 0; j < k; j++) {
- currentSum = currentSum + arry[i + j];
- }
- maxSum = Math.max(currentSum, maxSum);
- }
- return maxSum;
- }
暴力法用了兩個嵌套的for循環(huán)，時間復雜度不理想，為O(k*n); 而滑動窗口算法可以解決嵌套循環(huán)問題，有效降低時間復雜度。
因為滑動窗口就是維護一個窗口，不斷滑動，然后更新答案。 我們用滑動窗口算法來走一波：
當k=2時，
- 我們可以維護一個長度為2的窗口，初始化第一個窗口值的總和，并保存起來
- 然后窗口不斷向右滑動，滑動過程中，與保存的最大值比較，并更新答案。
- 窗口直到滑到最右邊才結(jié)束。
當k=3時，類似的
- 我們可以維護一個長度為3的窗口，初始化第一個窗口值的總和，并保存起來
- 然后窗口不斷向右滑動，滑動過程中，與保存的最大值比較，并更新答案。
- 窗口直到滑到最右邊才結(jié)束。
于是，我們就可以寫代碼啦：
- public int maxSum1(int[] arry, int k) {
- int size = arry.length;
- if (size < k) {
- return -1;
- }
- //初始化第一個窗口值的總和
- int maxSum = 0;
- for (int i = 0; i < k; i++) {
- maxSum = maxSum + arry[i];
- }
- int sum = maxSum;
- for (int i = k; i < size; i++) {
- sum = sum + arry[i] - arry[i - k];
- maxSum = Math.max(maxSum,sum);
- }
- return maxSum;
- }
使用了滑動窗口，時間復雜度，只需要O(n)就可以解決啦。
滑動窗口可以解決哪些問題
哪些leetcode的題目，我們可以用滑動窗口去解決呢?
一般情況，子串問題，如什么最小覆蓋子串、長度最小的子數(shù)組等等，都可以考慮使用滑動窗口算法。比較經(jīng)典的滑動窗口題目有這些：
- 無重復字符的最長子串
- 最小覆蓋子串
- 串聯(lián)所有單詞的子串
- 至多包含兩個不同字符的最長子串
- 長度最小的子數(shù)組
- 滑動窗口最大值
- 字符串的排列
- 最小窗口子序列
都是leetcode的原題，大家可以去leetcode官網(wǎng)找找手感哈。
滑動窗口框架套路
滑動窗口的大致邏輯框架，偽代碼如下：
- int left =0，right = 0;
- while (right < s.size()){
- //增大窗口
- window.add(s[right]);
- right++;
- while (window needs shrink){
- //縮小窗口
- window.remove (s[left]);
- left ++;
- }
- }
基本流程就是醬紫：
- 首先呢，就是獲取原字符串的長度。
- 接著維護一個窗口(數(shù)組、哈希、隊列)
- 窗口一步一步向右擴展
- 窗口在向右擴展滑動過程，需要判斷左邊是否需要縮減
- 最后比較更新答案
我們用這個框架，嘗試去解一道leetcode的真題吧。
題目：給定一個字符串 s ，請你找出其中不含有重復字符的最長子串的長度。
實例1：
- 輸入: s = "abcabcbb"
- 輸出: 3
- 解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。
示例 2:
- 輸入: s = "bbbbb"
- 輸出: 1
- 解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1。
因為需要判斷是否存在重復字符，所以，我們用一個哈希集合(HashSet)來作為窗口
- int lengthOfLongestSubstring(String s){
- //獲取原字符串的長度
- int len = s.length();
- //維護一個哈希集合的窗口
- Set<Character> windows = new HashSet<>();
- int left=0,right =0;
- int res =0;
- while(right<len){
- char c = s.charAt(right);
- //窗口右移
- right++;
- //判斷是否左邊窗口需要縮減，如果已經(jīng)包含，那就需要縮減
- while(windows.contains(c)){
- windows.remove(s.charAt(left));
- left++;
- }
- windows.add(c);
- //比較更新答案
- res = Math.max(res,windows.size());
- }
- return res;
- }
leetcode案例分析
我們再來看一道leetcode真題，加深一下印象哈。
題目：給你一個字符串S、一個字符串T。返回S中涵蓋T所有字符的最小子串。如果S中不存在涵蓋T所有字符的子串，則返回空字符串 "" 。
實例1：
- 輸入：s = "ADOBECODEBANC", t = "ABC"
- 輸出："BANC"
實例2：
- 輸入：s = "a", t = "a"
- 輸出："a"
我們還是套用這個框架流程：
- - 首先呢，就是獲取原字符串的長度。
- - 接著維護一個窗口(數(shù)組、哈希、隊列)
- - 窗口一步一步向右擴展
- - 窗口在向右擴展滑動過程，需要判斷左邊是否需要縮減
- - 最后比較更新答案
獲取原字符串的長度。
這個比較簡單，因為原題還是需要有左右指針去遍歷字符串S的。
- int len = S.length();
接著維護一個窗口(數(shù)組、哈希、隊列)、右移、左邊縮減
我們可以先定義一個最小的窗口，長度為0。定義窗口時，我們得想下：窗口什么時候右移，什么時候左邊縮減，怎么比較更新答案。
最小的窗口什么時候可以右移呢?因為題目要求涵蓋T的所有子串，所以，窗口一開始就可以右移，直到包含T的所有字母
顯然，窗口字符串ADOBEC，是S中涵蓋T所有字符的第一個子串。但是呢，我們要找的是最小子串，ADOBEC還不一定是最小的。因為：
- 1.當前窗口可能包含一個滿足題目條件的，更小的子窗口字符串。(可以左邊縮減)
- 2.窗口還沒滑到的地方，可能包含一個滿足條件的，更小的字符串。(可以窗口繼續(xù)右移)
找到第一個滿足條件的窗口字符串ADOBEC后，為了尋找更小的子窗口字符串。我們可以：
- 1.左邊縮減，如果縮小的窗口仍然滿足包含T所有字母，那當前窗口就可能是最小子串。存儲下來(就類似于滑動窗口框架的更新答案哈)，然后繼續(xù)從左縮減窗口。
- 2.如果縮小窗口不能滿足包含T的所有字母，這時候就可以停止窗口的左邊縮減，轉(zhuǎn)而向右擴大窗口啦。
窗口先左邊縮減，再右移動，保存滿足條件的窗口
不斷重復以上的步驟，把找到滿足條件的窗口保存下來，比較得出最小的子串。示例滿足條件的最小子串是BANC
這道題的難點，其實是如何判斷S的子串包含T，我們一起來看下代碼吧：
- class Solution {
- public String minWindow(String s, String t) {
- if (s.length() == 0 || s.length() < t.length()) {
- return "";
- }
- int sLen = s.length();
- Map<Character, Integer> lookup = new HashMap<>();
- for (int i = 0; i < sLen; i++) {
- lookup.put(s.charAt(i), 0);
- }
- for (int i = 0; i < t.length(); i++) {
- Character c = t.charAt(i);
- if (lookup.containsKey(c)) {
- lookup.put(c, lookup.get(c) + 1);
- } else {
- return "";
- }
- }
- int left = 0;
- int right = 0;
- int minLen = Integer.MAX_VALUE;
- int tCount = t.length();
- String result = "";
- while (right < sLen) {
- char c = s.charAt(right);
- if (lookup.get(c) > 0) tCount--;
- lookup.put(c, lookup.get(c) - 1);
- //窗口右移
- right++;
- //已經(jīng)包含T的所有字母
- while (tCount == 0) {
- //比較更新答案
- if (minLen > right - left) {
- minLen = right - left;
- result = s.substring(left, right);
- }
- char c2 = s.charAt(left);
- if (lookup.get(c2) == 0) tCount++;
- lookup.put(c2, lookup.get(c2) + 1);
- //窗口從左邊縮減
- left++;
- }
- }
- return result;
- }
- }
leetcode提交結(jié)果如下：
