1.题目描述：
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
2.分析
- 这个问题首先想到的必定是暴力解法，那就是遍历两遍这个字符串，找到其中的所有子串，求得最长的子串长度。当然如果这么解的话，时间复杂度必然会达到让人难以接受的O(n2)。
- 利用滑动窗口的原理
- 首先设立一个字典
last来保存所有字母最后出现的位置 - 接着设定一个指针
left来保存最左边的合法位置，当if s[i] in last and last[s[i]]>= left:这个条件成立的时候，说明目前的子串中有相同字母，需要更新合法位置left,更新的值就是left = last[s[i]] + 1，代表排除上一个相同字符后，left的合法的位置 - 在python做算法题的时候，要时刻想着能否使用字典这个数据结构，来优化自己的算法，空间换时间
3.解决
- 暴力遍历法
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
res_count = 0 # 最大结果
res_str = '' # 最长字符串
for i in range(len(s)): # 循环这么多次
max_str = ''
count = 0
for j in s[i:]:
if j not in max_str:
count += 1
max_str += j
if count > res_count:
res_count = count
res_str = max_str
else:
break
return res_count
- 滑动窗口法（利用字典hash表的查询优势）
class Solution(object):
def lengthOfLongestSubstring(self, s):
last = {} # 保存每一个字母所在的最后位置
left,ans=0,0 # left为保存当前合法位置
for i in range(len(s)):
if s[i] in last and last[s[i]]>= left:
left = last[s[i]] + 1 # 当遍历到的字母存在在last字典当中，且字典中的值大于或者等于合法位置left，则加1
last[s[i]] = i # 更新字母最后出现的位置
ans = max(ans,i-left+1) # 更新最长子串，这个也是一个类似动态规划的问题
return ans
