漫畫：滑動窗口系列 第二講（無重複字元的最長子串）

• 2020 年 3 月 30 日
• 筆記

在上一節中，我們使用雙端隊列完成了滑動窗口的一道頗為困難的題目，以此展示了什麼是滑動窗口。在本節中我們將繼續深入分析，探索滑動窗口題型一些具有模式性的解法。

01 滑動窗口介紹

對於大部分滑動窗口類型的題目，一般是考察字元串的匹配。比較標準的題目，會給出一個模式串B，以及一個目標串A。然後提出問題，找到A中符合對B一些限定規則的子串或者對A一些限定規則的結果，最終再將搜索出的子串完成題意中要求的組合或者其他。

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

又或者：給你一個字元串 S、一個字元串 T，請在字元串 S 裡面找出：包含 T 所有字母的最小子串。

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

都是屬於這一類的標準題型。而對於這一類題目，我們常用的解題思路，是去維護一個可變長度的滑動窗口。無論是使用雙指針，還是使用雙端隊列，又或者用游標等其他奇技淫巧，目的都是一樣的。

Now，我們通過一道題目來進行具體學習：

02 第3題：無重複字元的最長子串

第3題：給定一個字元串，請你找出其中不含有重複字元的 最長子串 的長度。

示例 1:

輸入: "abcabcbb"

輸出: 3

解釋: 因為無重複字元的最長子串是 "abc"，所以其長度為 3。

示例 2:

輸入: "bbbbb"

輸出: 1

解釋: 因為無重複字元的最長子串是 "b"，所以其長度為 1。

示例 3:

輸入: "pwwkew"

輸出: 3

解釋: 因為無重複字元的最長子串是 "wke"，所以其長度為 3。

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

03 題解分析

直接分析題目，假設我們的輸入為「abcabcbb」，我們只需要維護一個窗口在輸入字元串中進行移動。如下圖：

當下一個元素在窗口沒有出現過時，我們擴大窗口。

當下一個元素在窗口中出現過時，我們縮小窗口，將出現過的元素以及其左邊的元素統統移出：

在整個過程中，我們記錄下窗口出現過的最大值即可。而我們唯一要做的，只需要儘可能擴大窗口。

那我們程式碼中通過什麼來維護這樣的一個窗口呢？anyway~ 不管是隊列，雙指針，甚至通過map來做，都可以。

我們演示一個雙指針的做法：

//java  public class Solution {      public static int lengthOfLongestSubstring(String s) {          int n = s.length();          Set<Character> set = new HashSet<>();          int result = 0, left = 0, right = 0;          while (left < n && right < n) {              //charAt：返回指定位置處的字元              if (!set.contains(s.charAt(right))) {                  set.add(s.charAt(right));                  right++;                  result = Math.max(result, right - left);              } else {                  set.remove(s.charAt(left));                  left++;              }          }          return result;      }  }  

通過觀察，我們能看出來。如果是最壞情況的話，我們每一個字元都可能會訪問兩次，left一次，right一次，時間複雜度達到了O(2N)，這是不可饒恕的。不理解的話看下圖：

假設我們的字元串為「abcdc」，對於abc我們都訪問了2次。

那如何來進一步優化呢？

其實我們可以定義字元到索引的映射，而不是簡單通過一個集合來判斷字元是否存在。這樣的話，當我們找到重複的字元時，我們可以立即跳過該窗口，而不需要對之前的元素進行再次訪問。

//java  public class Solution {      public static int lengthOfLongestSubstring(String s) {          int n = s.length(), result = 0;          Map<Character, Integer> map = new HashMap<>();          for (int right = 0, left = 0; right < n; right++) {              if (map.containsKey(s.charAt(right))) {                  left = Math.max(map.get(s.charAt(right)), left);              }              result = Math.max(result, right - left + 1);              map.put(s.charAt(right), right + 1);          }          return result;      }  }  

修改之後，我們發現雖然時間複雜度有了一定提高，但是還是比較慢！如何更進一步的優化呢？我們可以使用一個256位的數組來替代hashmap，以進行優化。（因為ASCII碼錶里的字元總共有128個。ASCII碼的長度是一個位元組，8位，理論上可以表示256個字元，但是許多時候只談128個。具體原因可以下去自行學習~）

//java  class Solution {      public int lengthOfLongestSubstring(String s) {          int len = s.length();          int result = 0;          int[] charIndex = new int[256];          for (int left = 0, right = 0; right < len; right++) {              char c = s.charAt(right);              left = Math.max(charIndex[c], left);              result = Math.max(result, right - left + 1);              charIndex[c] = right + 1;          }          return result;      }  }  

我們發現優化後時間複雜度有了極大的改善！這裡簡單說一下原因，對於數組和hashmap訪問時，兩個誰快誰慢不是一定的，需要思考hashmap的底層實現，以及數據量大小。但是在這裡，因為已知了待訪問數據的下標，可以直接定址，所以極大的縮短了查詢時間。

04 啰啰嗦嗦

本題基本就到這裡。最後要說的，一般建議如果要分析一道題，我們要壓縮壓縮再壓縮，抽繭剝絲一樣走到最後，儘可能的完成對題目的優化。不一定非要自己想到最優解，但絕對不要局限於單純的完成題目，那樣將毫無意義！

最後，原創文章實在不易…希望大家可以幫忙轉發~不勝感激~（記得打卡）

轉發是對我最大的支援！

註：本系列所有教程中都不會用到複雜的語言特性，大家不需要擔心沒有學過語法知識。演算法思想最重要，使用各語言純屬本人愛好。同時，本系列所有程式碼均在leetcode上進行過測試運行，保證其嚴謹性！