LeetCode第3題：無重復(fù)字符的最長子串
Ps：本系列文章只為記錄自己刷LeetCode過程中的解題過程和思路。
題目描述：
給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的最長子串的長度。
示例 1：
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"，所以其長度為 3。
示例 2：
輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "b"，所以其長度為 1。
示例 3：
輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是"wke"，所以其長度為 3。
請(qǐng)注意，你的答案必須是 子串 的長度，"pwke"是一個(gè)子序列，不是子串。
解題過程和思路：
這道題的題目很明確，就是找序列中的無重復(fù)字符的最長子串。暴力解法的思路很簡單：遍歷序列，假設(shè)序列中的每個(gè)字符都可能為所求最長子串的第一個(gè)字符，每個(gè)字符都往后遍歷得到最長的子串，總共可以得到n個(gè)子串，最后比較各子串的長度即可。然而，偷偷看了大佬們的做法之后，發(fā)現(xiàn)了一個(gè)滑動(dòng)窗口很巧妙的應(yīng)用：每次發(fā)現(xiàn)重復(fù)肯定是窗口中已有不重復(fù)序列中的某個(gè)字符和新探索的字符重復(fù)發(fā)生了沖突，那么每次在發(fā)生沖突的時(shí)候?qū)⒋翱谥械哪莻€(gè)字符以及之前的字符踢出滑動(dòng)窗口即可，窗口每滑動(dòng)一步便記錄當(dāng)前窗口大小和歷史窗口大小的長度，大者為當(dāng)前探索得到的最長子串長度。待窗口滑動(dòng)到序列的最右端，我們也可以找出最長子串的長度了。（同樣地可以用字典來建模，提高在窗口中重復(fù)節(jié)點(diǎn)的搜索速度。）
解題收獲：
滑動(dòng)窗口的應(yīng)用，記住啦。
代碼展示：
class Solution(object):
def lengthOfLongestSubstring(self, s):
# 滑動(dòng)窗口解法
"""
:type s: str
:rtype: int
"""
max_l = 0 # 記錄目前搜索到的最大字串長度
p1 = p2 = 0 # 雙指針指示滑動(dòng)窗口的兩端，窗口內(nèi)的字串長度為 p2-p1
d = {} # 利用字典記錄目前搜索到的元素，用來查找是否有重復(fù)（將元素值作為鍵值，用字典查找快?。?
for index, c in enumerate(s): # 遍歷一遍字符串
if c not in d:
d[c] = index # 如果當(dāng)前字符不在字典中就加入，鍵值為元素值
p2 += 1 # 窗口右指針向右滑動(dòng)1格
else:
if d[c] + 1 > p1: # 兩個(gè)指針都只能往右移動(dòng)，如果不是很懂，“abba” 人工模擬這種情況即可
p1 = d[c] + 1 # 右指針移動(dòng)到重復(fù)的元素的右邊一位，將左邊的重復(fù)元素踢出窗口
p2 += 1 # 右指針繼續(xù)往右滑動(dòng)1格
d[c] = index # 字典記錄重復(fù)元素的最新的索引值
max_l = max(p2-p1, max_l) # 對(duì)比當(dāng)前最大長度和歷史最大長度，替換歷史最大長度
return max_l
結(jié)果展示：
