LeetCode刷題實戰(zhàn)3：最長不重復(fù)子串
算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做最長不重復(fù)子串，這道題很有意思，我們先來看題面：
Given a string, find the length of the longest substring without repeating characters.
https://leetcode.com/problems/longest-substring-without-repeating-characters/
翻譯
題目只有一句話：給定一個字符串，要求返回不包含重復(fù)字符的最長子串的長度。
Example 1:Input: "abcabcbb"Output: 3Explanation: The answer is "abc", with the length of 3.Example 2:Input: "bbbbb"Output: 1Explanation: The answer is "b", with the length of 1.Example 3:Input: "pwwkew"Output: 3Explanation: 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.
分析
我們先從最簡單的方法開始，最容易想到的算法就是暴力枚舉。我們可以遍歷出這個字符串當(dāng)中所有的子串，之后再判斷這個子串當(dāng)中有沒有出現(xiàn)重復(fù)的元素。如果沒有重復(fù)的元素，那么我們就更新答案。
在開始編碼之前，我們先仔細(xì)觀察樣例：
種。
ret = 0
for i in range(n):
char_set = set()
mid_ret = 0
for j in range(i + 1, n):
if S[j] in char_set:
mid_ret = j - i
break
else:
char_set.add(S[j])
ret = max(mid_ret, ret)
return ret
這種方法的復(fù)雜度就很好算了，對于S而言，它一共有n個位置可以作為起始，每個起始位置，最多遍歷n次，所以整體的復(fù)雜度應(yīng)該是
。
到這里，基本上是我們通過平常思維能夠想到的極致了，但是它遠(yuǎn)不是算法的極值。這道題還存在很大的優(yōu)化空間，在我們繼續(xù)探索之前，我們需要先來學(xué)習(xí)一個新的算法。它的名字叫做“尺取法”，在一些課本當(dāng)中也被稱為two pointer算法或者是兩指針?biāo)惴ǎ步谢瑒哟翱谒惴ā?/p>
算法的本意是，在一些對區(qū)間有所限制的問題當(dāng)中，我們可以通過維護(hù)合法區(qū)間的左右邊界。通過區(qū)間移動找出所有合法的區(qū)間，最后找到最終的答案。
在本題當(dāng)中，我們可以把一個不包含重復(fù)字符的子串當(dāng)做是原字符串的一個合法區(qū)間。比如在字符串 “abcabcbb” 當(dāng)中[0, 2]就是一個合法區(qū)間。我們用兩個記錄下標(biāo)的指針l和r來記錄這個區(qū)間的左右端點，注意這里的區(qū)間我們用的是閉區(qū)間。也就是說 l=0，r=2，區(qū)間表示好了，怎么移動區(qū)間呢？
[a b c] a b c b b
很簡單，我們每次往右移動一位，也就是r += 1，區(qū)間變成：
[a b c a] b c b b
r往右移動一位，就會讀入新的字符，那樣整個區(qū)間的合法性可能就破壞了。比如我們r加1了之后，讀入了a，字符串中多了一個a，那就不是合法區(qū)間了。
沒關(guān)系，我們還有區(qū)間的左邊界，我們可以再移動區(qū)間的左邊界，退出一些字符，直到區(qū)間重新變成合法區(qū)間為止，在這個例子當(dāng)中，l只需要移動一位就可以滿足條件：
a [b c a] b c b b
也就是說新的區(qū)間變成了[1, 3]，這樣就完成了區(qū)間的移動。如果r移動了之后，依舊沒有出現(xiàn)重復(fù)字符呢？沒關(guān)系，我們繼續(xù)往下移動就可以了。在這題當(dāng)中，[0, 0]一定是一個合法的區(qū)間，我們可以從[0, 0]開始，通過移動的方式遍歷出所有的合法區(qū)間。這些合法區(qū)間當(dāng)中，一定有一個是最終的答案，那么我們的問題也就解決了。
我們再來看一下這種算法的復(fù)雜度，它的復(fù)雜度是
。有人會說，我們用了兩個指針，不應(yīng)該也是的復(fù)雜度嗎？其實不然，看復(fù)雜度不能簡單只看用了幾個循環(huán)變量，而需要分析算法當(dāng)中究竟執(zhí)行了多少計算量。怎么證明算法復(fù)雜度呢？我們怎么知道窗口到底移動了多少次呢？
不知道移動了多少次也可以，方法很簡單，我們分析最壞的情況。算法的起始狀態(tài)是l=0, r=0。當(dāng)r=n時算法結(jié)束，我們不知道此時l等于多少，不過沒關(guān)系。在算法運(yùn)行的當(dāng)中，l和r都是遞增的，每次窗口移動最多增加1，那么最多應(yīng)該執(zhí)行了2n次（l和r各移動n次）。如此一來，顯然這是一個的算法。
算法講完了，還有一個細(xì)節(jié)沒講清楚，我們怎么維護(hù)區(qū)間合法呢？
也很簡單，我們維護(hù)一個map，記錄區(qū)間內(nèi)的字符出現(xiàn)了多少次。我們遇到新的字符，就在map中加一，退出字符，就在map中減一。
Talk is cheap, show me the code。我們寫出code來看看：
l, r = 0, 0
ret = 0
char_dict = {}
char_dict[S[0]] = 1
for r in range(1, n):
char_dict[S[r]] += 1
# 當(dāng)S[r]位置的字符大于1，說明區(qū)間非法，開始移動區(qū)間左側(cè)
# 最多l(xiāng)=r時結(jié)束，不用擔(dān)心越界
while char_dict[S[r]] > 1:
char_dict[S[l]] -= 1
l += 1
ret = max(ret, r - l + 1)
return ret
，但是并沒有結(jié)束，這題還有優(yōu)化的空間。l, r = 0, 0
ret = 0
char_dict = {}
char_dict[S[0]] = 0
for r in range(1, n):
# char_dict[S[r]] >= l這個判斷是精髓
if S[r] in char_dict and char_dict[S[r]] >= l:
l = char_dict[S[r]] + 1
char_dict[S[r]] = r
ret = max(ret, r - l + 1)
return ret
到這里，這道題就算是講解完了。尺取法這個算法雖然不難，但是仔細(xì)琢磨挺有意思。如果有沒有理解的同學(xué)，可以結(jié)合代碼以及樣例仔細(xì)思考一下，算法不難，我想大家都能學(xué)會，衷心希望大家都能有所收獲。
如果喜歡本文，請順手點個贊或者轉(zhuǎn)發(fā)吧。
上期推文：
LeetCode刷題實戰(zhàn)1：在數(shù)組上遍歷出花樣