字符串的子串求解類問題是一整個(gè)系列的方法，正好用這道題作為我個(gè)人學(xué)習(xí)的一個(gè)總結(jié)吧。
作為一個(gè)沒有訓(xùn)練過特定解法的新手，能夠想到的最直觀方法應(yīng)該就是暴力求解法，這個(gè)方法時(shí)間復(fù)雜度必然很高，但是好在思路清晰，也容易上手，所以就先從暴力法開始吧。

題目描述：

給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。

示例 1:

輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3。

示例 2

輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "b"，所以其長(zhǎng)度為 1。

示例 3:

輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "wke"，所以其長(zhǎng)度為 3。
請(qǐng)注意，你的答案必須是 子串 的長(zhǎng)度，"pwke" 是一個(gè)子序列，不是子串。

暴力求解法

• 我的初始思路：
  維護(hù)一個(gè)子串sub_string，外層循環(huán)按照給定字符串s每一個(gè)字符順序掃描，并且和子串每一個(gè)字符進(jìn)行比較（這里子串掃描應(yīng)該從后往前），一旦當(dāng)前字符在子串中找到相同的字符，那么子串就從相同字符前一個(gè)那里截?cái)?，然后把新字符加在結(jié)尾。每輪掃描后更新最長(zhǎng)子串的長(zhǎng)度，循環(huán)結(jié)束后返回。

• 代碼：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        sub_string = ''
        lens = 0
        for i in range(len(s)):
            if sub_string:
                for j in range(len(sub_string)-1,-1,-1):
                    if s[i] == sub_string[j]:
                        sub_string = sub_string[j+1:]
                        break
            sub_string+=s[i]
            #print(sub_string)
            lens = max(lens, len(sub_string))
        return lens

• 結(jié)果：
  因?yàn)閮蓪忧短籽h(huán)的使用，結(jié)果時(shí)間復(fù)雜度約為O（n^2），那么速度也是可想而知的慢……（還好沒超時(shí)）

執(zhí)行用時(shí) :372 ms, 在所有 python3 提交中擊敗了13.76%的用戶

我這個(gè)速度是注定要被人嘲笑的（還好我臉皮厚），接下來就是進(jìn)階之路啦。

暴力求解法的進(jìn)化思路 -- 滑塊法

• 思路：
  我在網(wǎng)上偶然發(fā)現(xiàn)了一個(gè)跟我的思路非常像，但是效率高了很多的解法。來自于簡(jiǎn)書冬小羊的這篇博客，可以去讀一下。
  這個(gè)解法優(yōu)化的點(diǎn)在于：

1. 不需要維護(hù)一個(gè)子串了，而采用哈希表的方式記錄每一個(gè)字符出現(xiàn)的次數(shù)，這樣就可以很方便的找到多余的字符。

2. 同時(shí)也就不需要遍歷子串找到截?cái)帱c(diǎn)。而是采用雙指針指向子串首尾的方式，一旦子串里有字符重復(fù)，那么就移動(dòng)子串頭一格，直到子串里沒有重復(fù)字符為止。其實(shí)這一步做的事情就相當(dāng)于截?cái)嘧哟恕?br>

   下面這張圖也來自于冬小羊的博客，大家可以直觀感受一下這個(gè)解法：
   滑動(dòng)法圖解

• 代碼：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        start = 0 # 子串起點(diǎn)指針
        end = 0 # 子串終點(diǎn)指針
        char_dict = dict() #統(tǒng)計(jì)子串中每一個(gè)字符出現(xiàn)的個(gè)數(shù)
        lens = 0

        for i in s:
            end += 1
            char_dict[i] = char_dict.get(i,0)+1
            while char_dict[i] > 1:
                char_dict[s[start]] -= 1
                start += 1
            lens = max(lens,end-start)
        return lens

• 結(jié)果：
  不得不說，這樣修改之后，效果真的是杠杠的

執(zhí)行用時(shí) :80 ms, 在所有 python3 提交中擊敗了78.88%的用戶

因?yàn)檫@樣其實(shí)只有一個(gè)循環(huán)，內(nèi)層因?yàn)榍擅钍褂弥羔樅凸１恚ň褪亲值浔恚┧源蟠筇嵘诉\(yùn)行效率，感謝網(wǎng)友朋友們的智慧。