需求
給定一個字符串贾漏，請你找出其中不含有重復字符的 最長子串 的長度沮稚。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3带到。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"靠娱，所以其長度為 1。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是 "wke"敛纲，所以其長度為 3喂击。
請注意，你的答案必須是 子串 的長度淤翔，"pwke" 是一個子序列翰绊，不是子串。
解決思路
方法一
- 遍歷字符串
字符未重復時拼接到中間字符串中旁壮，出現(xiàn)重復字符時监嗜，先將中間字符串追加到中間結(jié)果list中；
在中間字符中找到重復字符的位置抡谐，從下一位開始截取后面的字符串裁奇，與重復字符拼接，重新賦值為中間字符串麦撵，繼續(xù)下次遍歷; - 遍歷完成后刽肠，需要將最后一個中間字符串添加到中間list中溃肪，這一步很容易被忽略；
- 最后通過生成器表達式結(jié)合max()函數(shù)音五，返回中間結(jié)果list中元素的最大長度惫撰。
- 參考代碼
def get_str_len(s):
tmp = ''
r = []
for i in range(len(s)):
if s[i] not in tmp:
tmp += s[i]
else:
r.append(tmp)
n = tmp.index(s[i])
tmp = tmp[n+1:] + s[i]
r.append(tmp)
return max(len(x) for x in r)
s = 'dvdf'
print(get_str_len(s))
3
方法二
- 方法二與方法一的思路相同，區(qū)別是不再產(chǎn)生中間結(jié)果list躺涝，而是每次遍歷時厨钻，返回最大的中間字符串長度；
- 類似這樣的坚嗜，不需要將所有符合條件的數(shù)據(jù)生成中間結(jié)果后夯膀，再進行篩選判斷，而是在遍歷的同時苍蔬，返回符合條件的數(shù)據(jù)诱建，該方法更簡潔優(yōu)雅，效率也OK银室。
- 參考代碼
def get_str_len(s):
tmp = ''
r = 0
for v in s:
if v not in tmp:
tmp += v
else:
n = tmp.index(v)
tmp = tmp[n+1:] + v
r = max(len(tmp), r)
return r
s = 'dvdf'
print(get_str_len(s))
3
方法三
- 該方法抽象出需求(無重復最長子串)的規(guī)律，通過簡單遍歷即可實現(xiàn)励翼，但是理解起來有難度蜈敢，更抽象，效率并卵有提升多少汽抚，感興趣的話抓狭，可以了解一下思路；
- 遍歷字符串
基于字符(key)和字符在字符串中的位置(value)構(gòu)建字典d造烁，存在重復字符時覆蓋原有元素否过，值變更為新的字符位置；
構(gòu)建2個變量n/m：
1）未出現(xiàn)重復字符前惭蟋，n為0苗桂、m為d中元素個數(shù)；
2）出現(xiàn)重復字符時：n為當前重復字符在字符串中上一次出現(xiàn)的位置告组，或者字符串中該重復字符之前其它重復字符在字符串中上一次出現(xiàn)的位置煤伟，取最大位置；m為當前字符在字符串中出現(xiàn)的位置木缝，減去重復字符的最大位置(n)便锨，即為最長的不重復子串。 - 參考代碼
def get_str_len(s):
d = {}
n, m = 0, 0
for i in range(len(s)):
if s[i] in d:
n = max(d[s[i]], n)
m = max(m, i + 1 - n)
d[s[i]] = i + 1
return m
s = 'dvdf'
print(get_str_len(s))
3
