標(biāo)簽（空格分隔）： 動(dòng)態(tài)規(guī)劃 滑動(dòng)窗口 散列表
傳送門：3. 無重復(fù)字符的最長(zhǎng)子串。這道題也是《劍指Offer》上第 48 題脏款。
給定一個(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è)子序列齐板，不是子串吵瞻。
解法1：哈希表 + 隔板法（好幾種寫法）
判斷一個(gè)元素有沒有出現(xiàn)過，使用哈希表是最自然的想法甘磨。
以下面的例子進(jìn)行說明：
判斷連續(xù)區(qū)間內(nèi)是否出現(xiàn)重復(fù)元素橡羞，可以使用 set，又要存儲(chǔ)位置济舆，所以使用 dict卿泽。
- 到索引為
的時(shí)候，出現(xiàn)重復(fù)滋觉，我們可以在
的下一個(gè)位置插一個(gè)“小木板”签夭，表示從這個(gè)“小木板”到當(dāng)前位置沒有重復(fù)。如果出現(xiàn)重復(fù)的索引在“小木板”之前椎侠，例如到索引
的時(shí)候第租，此時(shí)“小木板”在索引
處，兩個(gè)
之間已經(jīng)有了兩個(gè)
Python 代碼1：（推薦寫法）
LeetCode 第 3 題：無重復(fù)字符的最長(zhǎng)子串-1
等價(jià)的寫法：（我的練習(xí)）
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
map = dict()
max_len = 0
# 可以認(rèn)為是標(biāo)定的起始
pointer = 0
for index, c in enumerate(s):
if c in map:
pointer = max(pointer, map[c] + 1)
max_len = max(max_len, index - pointer + 1)
# 每次遍歷都更新當(dāng)前遍歷到的字母的位置
map[c] = index
return max_len
if __name__ == '__main__':
s = 'pwwkew'
solution = Solution()
result = solution.lengthOfLongestSubstring(s)
print(result)
需要注意的一點(diǎn)是：只有重復(fù)出現(xiàn)的位置大于標(biāo)定點(diǎn)的時(shí)候儡羔，才要更新，更新的位置是當(dāng)前位置 + 1璧诵。即只要出現(xiàn)重復(fù)汰蜘，隔板就向后移動(dòng)一位，然后每一輪都計(jì)算當(dāng)前與隔板的距離之宿。
Python 代碼2：（不如上面的代碼語義清晰）
class Solution:
def lengthOfLongestSubstring(self, s):
# 特判
l = len(s)
if l < 2:
return l
# 隔板法
# key:字符族操，val 出現(xiàn)的索引
map = dict()
point = 0
res = 1
for i in range(l):
# 關(guān)鍵1：map[s[i]] >= point，等于是可以的
if s[i] in map and map[s[i]] >= point:
# 先把隔板向后移動(dòng)一位
point = map[s[i]] + 1
# 然后記錄最長(zhǎng)不重復(fù)子串的長(zhǎng)度
res = max(res, i - point + 1)
# 關(guān)鍵2：無論如何都更新位置
map[s[i]] = i
return res
等價(jià)的寫法：（我的練習(xí)）
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
l = len(s)
if l <= 1:
return l
point = 0
map = dict()
result = 0
for index, alpha in enumerate(s):
if alpha in map and map[alpha] >= point:
point = map[alpha] + 1
# 每次要做兩件事：1比被、計(jì)算無重復(fù)子串長(zhǎng)度
result = max(result, index - point + 1)
# 2色难、更新索引
map[alpha] = index
return result
解法2：動(dòng)態(tài)規(guī)劃
dp[i]：以 s[i] 結(jié)尾的最長(zhǎng)不重復(fù)子串，這個(gè)狀態(tài)的設(shè)置與最長(zhǎng)上升子序列等缀、最大連續(xù)子數(shù)組是一樣的枷莉。
下面考慮 dp[i] 和 dp[i-1] 之間的關(guān)系。關(guān)鍵在于 dp [i-1] 與距離出現(xiàn)相同字符的時(shí)候尺迂，兩個(gè)相同字符的距離的比較笤妙。
LeetCode 第 3 題：無重復(fù)字符的最長(zhǎng)子串-2
LeetCode 第 3 題：無重復(fù)字符的最長(zhǎng)子串-3
Python 代碼：
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# 特判
l = len(s)
if l < 2:
return l
# dp[i] 表示以 s[i] 結(jié)尾的最長(zhǎng)不重復(fù)子串的長(zhǎng)度
# 因?yàn)樽约嚎隙ㄊ遣恢貜?fù)子串，所以初始值設(shè)置為 1
dp = [1 for _ in range(l)]
map = dict()
map[s[0]] = 0
for i in range(1, l):
if s[i] in map:
if i - map[s[i]] > dp[i - 1]:
dp[i] = dp[i - 1] + 1
else:
dp[i] = i - map[s[i]]
else:
dp[i] = dp[i - 1] + 1
# 設(shè)置字符與索引鍵值對(duì)
map[s[i]] = i
# 最后拉通看一遍最大值
return max(dp)
解法3：滑動(dòng)窗口噪裕、雙指針
Python 代碼：推薦寫法
# 滑動(dòng)窗口的做法
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# 特判
size = len(s)
if size < 2:
return size
l = 0
r = -1
counter = [0 for _ in range(256)]
res = 1
while l < size:
# 嘗試走一步蹲盘，如果可以走，就計(jì)算
if r + 1 < size and counter[ord(s[r + 1])] == 0:
# 表示沒有重復(fù)元素膳音，r 可以加 1
counter[ord(s[r + 1])] += 1
r += 1
else:
# 有重復(fù)元素召衔，左邊就要減 1
counter[ord(s[l])] -= 1
l += 1
res = max(res, r - l + 1)
return res
Python 代碼：滑動(dòng)窗口寫法2
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# 特判
size = len(s)
if size < 2:
return size
l = 0
r = -1
counter = [0 for _ in range(256)]
res = 1
while l < size:
# 首先"右指針"不斷向右邊嘗試，走到出現(xiàn)重復(fù)的最右邊
while r + 1 < size and counter[ord(s[r + 1])] == 0:
# 表示沒有重復(fù)元素祭陷，r 可以加 1
counter[ord(s[r + 1])] += 1
r += 1
# 此時(shí)苍凛，記錄不重復(fù)子串是"左指針"固定時(shí)候最長(zhǎng)
res = max(res, r - l + 1)
# 考慮移動(dòng)"左指針"
# 此時(shí) s[r+1] 就是已經(jīng)掃過的區(qū)間里重復(fù)的元素，要把它剔除出去
while r + 1 < size and s[l] != s[r + 1]:
# 有重復(fù)元素兵志，左邊就要減 1
counter[ord(s[l])] -= 1
l += 1
# 出了上一個(gè)循環(huán)以后醇蝴，還要再把左指針向右移動(dòng)一格，否則右指針不能向右移動(dòng)
counter[ord(s[l])] -= 1
l += 1
return res
（本節(jié)完）
