前言

我們刷leetcode的時(shí)候，經(jīng)常會(huì )遇到滑動(dòng)窗口類(lèi)型題目?；瑒?dòng)窗口問(wèn)題非常經(jīng)典，也很有技巧性，一般大廠(chǎng)也喜歡問(wèn)。今天跟大家一起來(lái)學(xué)習滑動(dòng)窗口的套路，文章如果有不正確的地方，歡迎大家指出哈，感謝感謝~

• 什么是滑動(dòng)窗口？
• 一道算法題走進(jìn)滑動(dòng)窗口
• 滑動(dòng)窗口可以用來(lái)解決哪些問(wèn)題?
• 滑動(dòng)窗口框架套路
• leetcode案例分析

什么是滑動(dòng)窗口

滑動(dòng)窗口這個(gè)詞，相信大家耳熟能詳啦。因為說(shuō)到TCP的時(shí)候，經(jīng)常談起滑動(dòng)窗口協(xié)議（Sliding Window Protocol）,它是TCP協(xié)議的一種應用，用于網(wǎng)絡(luò )數據傳輸時(shí)的流量控制，以避免擁塞的發(fā)生。

TCP頭部有個(gè)字段叫win，也即那個(gè)16位的窗口大小，它告訴對方本端的TCP接收緩沖區還能容納多少字節的數據，這樣對方就可以控制發(fā)送數據的速度，從而達到流量控制的目的。

TCP的滑動(dòng)窗口在某一個(gè)時(shí)刻就是固定窗口大小的滑動(dòng)窗口，隨著(zhù)網(wǎng)絡(luò )流量等因素改變窗口大小也會(huì )隨著(zhù)改變。算法中的滑動(dòng)窗口有點(diǎn)類(lèi)似，就是維護一個(gè)窗口（隊列/數組），不斷滑動(dòng)，然后更新答案?；瑒?dòng)窗口，指的是這樣一類(lèi)問(wèn)題的求解方法，在數組上通過(guò)雙指針同向移動(dòng)而解決的一類(lèi)問(wèn)題。

一個(gè)例子走進(jìn)滑動(dòng)窗口算法

我們來(lái)看一道算法題吧：給定一個(gè)整數數組，計算長(cháng)度為k的連續子數組的最大總和。

輸入：arr [] = {100,200,300,400}  k = 2

輸出：700

解釋?zhuān)?00 + 400 = 700

看到這個(gè)題目，我們馬上想到暴力法去解決了，兩個(gè)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;
    }

暴力法用了兩個(gè)嵌套的for循環(huán)，時(shí)間復雜度不理想，為O(k*n); 而滑動(dòng)窗口算法可以解決嵌套循環(huán)問(wèn)題，有效降低時(shí)間復雜度。

因為滑動(dòng)窗口就是維護一個(gè)窗口，不斷滑動(dòng)，然后更新答案。 我們用滑動(dòng)窗口算法來(lái)走一波：

當k=2時(shí)，

• 我們可以維護一個(gè)長(cháng)度為2的窗口，初始化第一個(gè)窗口值的總和，并保存起來(lái)
• 然后窗口不斷向右滑動(dòng)，滑動(dòng)過(guò)程中，與保存的最大值比較，并更新答案。
• 窗口直到滑到最右邊才結束。

當k=3時(shí)，類(lèi)似的

• 我們可以維護一個(gè)長(cháng)度為3的窗口，初始化第一個(gè)窗口值的總和，并保存起來(lái)
• 然后窗口不斷向右滑動(dòng)，滑動(dòng)過(guò)程中，與保存的最大值比較，并更新答案。
• 窗口直到滑到最右邊才結束。

于是，我們就可以寫(xiě)代碼啦：

   public int maxSum1(int[] arry, int k) {
        int size = arry.length;

        if (size < k) {
            return -1;
        }

        //初始化第一個(gè)窗口值的總和
        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;
    }

使用了滑動(dòng)窗口，時(shí)間復雜度，只需要O(n)就可以解決啦。

滑動(dòng)窗口可以解決哪些問(wèn)題

哪些leetcode的題目，我們可以用滑動(dòng)窗口去解決呢？

一般情況，子串問(wèn)題，如什么最小覆蓋子串、長(cháng)度最小的子數組等等，都可以考慮使用滑動(dòng)窗口算法。比較經(jīng)典的滑動(dòng)窗口題目有這些：

• 無(wú)重復字符的最長(cháng)子串
• 最小覆蓋子串
• 串聯(lián)所有單詞的子串
• 至多包含兩個(gè)不同字符的最長(cháng)子串
• 長(cháng)度最小的子數組
• 滑動(dòng)窗口最大值
• 字符串的排列
• 最小窗口子序列

都是leetcode的原題，大家可以去leetcode官網(wǎng)找找手感哈。

滑動(dòng)窗口框架套路

滑動(dòng)窗口的大致邏輯框架，偽代碼如下：

int left =0，right = 0;
while (right < s.size()){
  //增大窗口
  window.add(s[right]);
  right++;
  
  while (window needs shrink){
    //縮小窗口
    window.remove (s[left]);
    left ++;
  }
}

基本流程就是醬紫：

• 首先呢，就是獲取原字符串的長(cháng)度。
• 接著(zhù)維護一個(gè)窗口（數組、哈希、隊列）
• 窗口一步一步向右擴展
• 窗口在向右擴展滑動(dòng)過(guò)程，需要判斷左邊是否需要縮減
• 最后比較更新答案

我們用這個(gè)框架，嘗試去解一道leetcode的真題吧。

題目：給定一個(gè)字符串 s ，請你找出其中不含有重復字符的最長(cháng)子串的長(cháng)度。

實(shí)例1：

輸入: s = "abcabcbb"
輸出: 3 
解釋: 因為無(wú)重復字符的最長(cháng)子串是 "abc"，所以其長(cháng)度為 3。

示例 2:

輸入: s = "bbbbb"
輸出: 1
解釋: 因為無(wú)重復字符的最長(cháng)子串是 "b"，所以其長(cháng)度為 1。

因為需要判斷是否存在重復字符，所以，我們用一個(gè)哈希集合（HashSet）來(lái)作為窗口

int lengthOfLongestSubstring(String s){
     //獲取原字符串的長(cháng)度
     int len = s.length();
     //維護一個(gè)哈希集合的窗口
     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案例分析

我們再來(lái)看一道leetcode真題，加深一下印象哈。

題目：給你一個(gè)字符串S、一個(gè)字符串T。返回S中涵蓋T所有字符的最小子串。如果S中不存在涵蓋T所有字符的子串，則返回空字符串 "" 。

實(shí)例1：

輸入：s = "ADOBECODEBANC", t = "ABC"
輸出："BANC"

實(shí)例2：

輸入：s = "a", t = "a"
輸出："a"

我們還是套用這個(gè)框架流程：

- 首先呢，就是獲取原字符串的長(cháng)度。
- 接著(zhù)維護一個(gè)窗口（數組、哈希、隊列）
- 窗口一步一步向右擴展
- 窗口在向右擴展滑動(dòng)過(guò)程，需要判斷左邊是否需要縮減
- 最后比較更新答案

獲取原字符串的長(cháng)度。

這個(gè)比較簡(jiǎn)單，因為原題還是需要有左右指針去遍歷字符串S的。

int len = S.length();

接著(zhù)維護一個(gè)窗口（數組、哈希、隊列）、右移、左邊縮減

我們可以先定義一個(gè)最小的窗口，長(cháng)度為0。定義窗口時(shí)，我們得想下：窗口什么時(shí)候右移，什么時(shí)候左邊縮減，怎么比較更新答案。

最小的窗口什么時(shí)候可以右移呢？因為題目要求涵蓋T的所有子串，所以，窗口一開(kāi)始就可以右移，直到包含T的所有字母

顯然，窗口字符串ADOBEC，是S中涵蓋T所有字符的第一個(gè)子串。但是呢，我們要找的是最小子串，ADOBEC還不一定是最小的。因為：

• 1.當前窗口可能包含一個(gè)滿(mǎn)足題目條件的，更小的子窗口字符串。（可以左邊縮減）
• 2.窗口還沒(méi)滑到的地方，可能包含一個(gè)滿(mǎn)足條件的，更小的字符串。（可以窗口繼續右移）

找到第一個(gè)滿(mǎn)足條件的窗口字符串ADOBEC后，為了尋找更小的子窗口字符串。我們可以：

• 1.左邊縮減，如果縮小的窗口仍然滿(mǎn)足包含T所有字母，那當前窗口就可能是最小子串。存儲下來(lái)（就類(lèi)似于滑動(dòng)窗口框架的更新答案哈），然后繼續從左縮減窗口。
• 2.如果縮小窗口不能滿(mǎn)足包含T的所有字母，這時(shí)候就可以停止窗口的左邊縮減，轉而向右擴大窗口啦。
  

窗口先左邊縮減，再右移動(dòng)，保存滿(mǎn)足條件的窗口

不斷重復以上的步驟，把找到滿(mǎn)足條件的窗口保存下來(lái)，比較得出最小的子串。示例滿(mǎn)足條件的最小子串是BANC

這道題的難點(diǎn)，其實(shí)是如何判斷S的子串包含T，我們一起來(lái)看下代碼吧：

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提交結果如下：

文章源自“撿田螺的小男孩