今天和大家聊的問題叫做最長不重複子串，這道題很有意思，我們先來看題面：

Given a string, find the length of the longest substring without repeating characters.

翻譯

題目只有一句話：給定一個字符串，要求返回不包含重複字符的最長子串的長度。

樣例

Example

1:​Input: "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

Example 2:

​Input: "bbbbb"

Output: 1

Explanation: The answer is "b", with the length of 1.

Example 3:

​Input: "pwwkew"

Output: 3

Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

分析

我們先從最簡單的方法開始，最容易想到的算法就是暴力枚舉。我們可以遍歷出這個字符串當中所有的子串，之後再判斷這個子串當中有沒有出現重複的元素。如果沒有重複的元素，那麼我們就更新答案。

在開始編碼之前，我們先仔細觀察樣例：

我們可以計算出這種算法的複雜度，假設字符串長度是n，那麼我們它的所有子串應該有n的平方種。

再乘上我們遍歷這個子串時候的長度，所以最後的結果是:

整體的複雜度是n的三方，顯然這樣的複雜度是無法接受的，下面我們進行第一個優化。

思考一個問題，在不能有重複字符的限制下，我們真的有必要枚舉所有的子串嗎？

其實是沒有的，在這個規則的限制下，對於字符串當中的每一個起始位置，我們能找到的最長的合法子串必然是確定而且是唯一的。換句話說，對於一個確切的開頭而言，我們只需要順著它一直往後遍歷，如果遇到的字符沒有出現過就繼續，如果已經出現過了，那麼當下的字符串就是這個開頭對應的最佳答案。

我們用樣例舉個例子：

假設S=abcabcbb

我們從S[0]開始，我們遍歷b，再遍歷c，接著遍歷a。a已經出現過了，所以abc就是以S[0]開頭的最佳答案。對於S當中的每一個位置，我們都可以找到它對應的局部最佳答案。之後，我們只需要在這當中找出最大的長度即可。

我們用Python寫出代碼：

這種方法的複雜度就很好算了，對於S而言，它一共有n個位置可以作為起始，每個起始位置，最多遍歷n次，所以整體的複雜度應該是n的平方。

到這裡，基本上是我們通過平常思維能夠想到的極致了，但是它遠不是算法的極值。這道題還存在很大的優化空間，在我們繼續探索之前，我們需要先來學習一個新的算法。它的名字叫做“尺取法”，在一些課本當中也被稱為two pointer算法或者是兩指針算法，也叫滑動窗口算法。

算法的本意是，在一些對區間有所限制的問題當中，我們可以通過維護合法區間的左右邊界。通過區間移動找出所有合法的區間，最後找到最終的答案。

在本題當中，我們可以把一個不包含重複字符的子串當做是原字符串的一個合法區間。比如在字符串 “abcabcbb” 當中[0, 2]就是一個合法區間。我們用兩個記錄下標的指針l和r來記錄這個區間的左右端點，注意這裡的區間我們用的是閉區間。也就是說 l=0，r=2，區間表示好了，怎麼移動區間呢？

[a b c] a b c b b

很簡單，我們每次往右移動一位，也就是r += 1，區間變成：

[a b c a] b c b b

r往右移動一位，就會讀入新的字符，那樣整個區間的合法性可能就破壞了。比如我們r加1了之後，讀入了a，字符串中多了一個a，那就不是合法區間了。

沒關係，我們還有區間的左邊界，我們可以再移動區間的左邊界，退出一些字符，直到區間重新變成合法區間為止，在這個例子當中，l只需要移動一位就可以滿足條件：

也就是說新的區間變成了[1, 3]，這樣就完成了區間的移動。如果r移動了之後，依舊沒有出現重複字符呢？沒關係，我們繼續往下移動就可以了。在這題當中，[0, 0]一定是一個合法的區間，我們可以從[0, 0]開始，通過移動的方式遍歷出所有的合法區間。這些合法區間當中，一定有一個是最終的答案，那麼我們的問題也就解決了。

我們再來看一下這種算法的複雜度，它的複雜度是O(n)。有人會說，我們用了兩個指針，不應該也是O(n^2)的複雜度嗎？其實不然，看複雜度不能簡單隻看用了幾個循環變量，而需要分析算法當中究竟執行了多少計算量。怎麼證明算法複雜度呢？我們怎麼知道窗口到底移動了多少次呢？

不知道移動了多少次也可以，方法很簡單，我們分析最壞的情況。算法的起始狀態是l=0, r=0。當r=n時算法結束，我們不知道此時l等於多少，不過沒關係。在算法運行的當中，

的算法。

算法講完了，還有一個細節沒講清楚，我們怎麼維護區間合法呢？

也很簡單，我們維護一個map，記錄區間內的字符出現了多少次。我們遇到新的字符，就在map中加一，退出字符，就在map中減一。

Talk is cheap, show me the code。我們寫出code來看看：

代碼看起來依然很簡潔，編碼複雜度幾乎沒有增加。到這裡，我們雖然已經將算法優化成了O(n)

，但是並沒有結束，這題還有優化的空間。

那麼，怎麼做進一步優化呢？

敏感的同學在觀察上面這段代碼的時候，可能會覺得中間的while循環有點彆扭。雖然我們經過分析l最多也就移動到r的位置，不會出現越界等問題，但看到循環裡套了循環還是會覺得不太舒服。

我們的下一個優化，就和這個循環有關。那麼怎麼才能把循環去掉呢？我們先從它產生的原因入手，我們之所以需要一個循環，是因為我們並不知道引起重複的S[r]這個字符在區間裡出現的位置在什麼地方，如果我們能夠知道，那麼就很簡單，我們

我們能不能知道呢？當然是可以的，需要我們對dict做一點點改動。我們dict不能再存儲字符出現的次數，我們需要存儲它最後一次出現的位置。這樣，我們對上面的代碼稍作修改就可以滿足要求了：

到這裡，這道題就算是講解完了。尺取法這個算法雖然不難，但是仔細琢磨挺有意思。如果有沒有理解的同學，可以結合代碼以及樣例仔細思考一下，算法不難，我想大家都能學會，衷心希望大家都能有所收穫。

如果喜歡本文，請順手點個“關注”吧。

閱讀更多 承志的算法課堂 的文章

關鍵字: 算法 題面 這道題