字符串的子串求解類問題是一整個(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)啵缓蟀研伦址釉诮Y(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)在于：
- 不需要維護(hù)一個(gè)子串了，而采用哈希表的方式記錄每一個(gè)字符出現(xiàn)的次數(shù)抛姑，這樣就可以很方便的找到多余的字符。
-
同時(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)友朋友們的智慧空猜。
