标签（空格分隔）： 动态规划 滑动窗口 散列表
传送门：3. 无重复字符的最长子串。这道题也是《剑指Offer》上第 48 题。
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:
输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:
输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
解法1：哈希表 + 隔板法（好几种写法）
判断一个元素有没有出现过，使用哈希表是最自然的想法。
以下面的例子进行说明：
判断连续区间内是否出现重复元素，可以使用 set，又要存储位置，所以使用 dict。
- 到索引为
的时候，出现重复，我们可以在
的下一个位置插一个“小木板”，表示从这个“小木板”到当前位置没有重复。如果出现重复的索引在“小木板”之前，例如到索引
的时候，此时“小木板”在索引
处，两个
之间已经有了两个
Python 代码1：（推荐写法）
LeetCode 第 3 题：无重复字符的最长子串-1
等价的写法：（我的练习）
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
map = dict()
max_len = 0
# 可以认为是标定的起始
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)
# 每次遍历都更新当前遍历到的字母的位置
map[c] = index
return max_len
if __name__ == '__main__':
s = 'pwwkew'
solution = Solution()
result = solution.lengthOfLongestSubstring(s)
print(result)
需要注意的一点是：只有重复出现的位置大于标定点的时候，才要更新，更新的位置是当前位置 + 1。即只要出现重复，隔板就向后移动一位，然后每一轮都计算当前与隔板的距离。
Python 代码2：（不如上面的代码语义清晰）
class Solution:
def lengthOfLongestSubstring(self, s):
# 特判
l = len(s)
if l < 2:
return l
# 隔板法
# key:字符，val 出现的索引
map = dict()
point = 0
res = 1
for i in range(l):
# 关键1：map[s[i]] >= point，等于是可以的
if s[i] in map and map[s[i]] >= point:
# 先把隔板向后移动一位
point = map[s[i]] + 1
# 然后记录最长不重复子串的长度
res = max(res, i - point + 1)
# 关键2：无论如何都更新位置
map[s[i]] = i
return res
等价的写法：（我的练习）
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、计算无重复子串长度
result = max(result, index - point + 1)
# 2、更新索引
map[alpha] = index
return result
解法2：动态规划
dp[i]：以 s[i] 结尾的最长不重复子串，这个状态的设置与最长上升子序列、最大连续子数组是一样的。
下面考虑 dp[i] 和 dp[i-1] 之间的关系。关键在于 dp [i-1] 与距离出现相同字符的时候，两个相同字符的距离的比较。
LeetCode 第 3 题：无重复字符的最长子串-2
LeetCode 第 3 题：无重复字符的最长子串-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] 结尾的最长不重复子串的长度
# 因为自己肯定是不重复子串，所以初始值设置为 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
# 设置字符与索引键值对
map[s[i]] = i
# 最后拉通看一遍最大值
return max(dp)
解法3：滑动窗口、双指针
Python 代码：推荐写法
# 滑动窗口的做法
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:
# 尝试走一步，如果可以走，就计算
if r + 1 < size and counter[ord(s[r + 1])] == 0:
# 表示没有重复元素，r 可以加 1
counter[ord(s[r + 1])] += 1
r += 1
else:
# 有重复元素，左边就要减 1
counter[ord(s[l])] -= 1
l += 1
res = max(res, r - l + 1)
return res
Python 代码：滑动窗口写法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:
# 首先"右指针"不断向右边尝试，走到出现重复的最右边
while r + 1 < size and counter[ord(s[r + 1])] == 0:
# 表示没有重复元素，r 可以加 1
counter[ord(s[r + 1])] += 1
r += 1
# 此时，记录不重复子串是"左指针"固定时候最长
res = max(res, r - l + 1)
# 考虑移动"左指针"
# 此时 s[r+1] 就是已经扫过的区间里重复的元素，要把它剔除出去
while r + 1 < size and s[l] != s[r + 1]:
# 有重复元素，左边就要减 1
counter[ord(s[l])] -= 1
l += 1
# 出了上一个循环以后，还要再把左指针向右移动一格，否则右指针不能向右移动
counter[ord(s[l])] -= 1
l += 1
return res
（本节完）
