题目:
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
思路：
无重复，最长子串。首先想到的是遍历字串比较，不存在相同key， length长度就+1，如果存在则移位，从下一位开始继续比较。
方法一：
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
length = upper = lower = 0 #长度变数初始赋值
while upper < len(s):
if s[upper] not in s[lower:upper]: #依次遍历字串单个字节内容，是否在字串范围中
upper +=1 #不在，下限+1，往下位继续遍历
length = max(length,len(s[lower:upper])) #获得当前已遍历出的子串的最大长度
else:
lower +=1 #当字串范围包含字节时，上限+1，跳过该位，往下位开始重新遍历
return length
执行用时 :84 ms, 在所有 Python 提交中击败了39.60%的用户
内存消耗 :12.8 MB, 在所有 Python 提交中击败了15.15%的用户
看起来这是笨方法，虽然我不懂算法最优解计算逻辑，但是明显感觉到这个方法每次都会从头开始遍历，有点浪费时间。
方法二：
思路：
方法一是通过字符串的index 来移位，那我可不可以通过array来做类似的事情呢？当然可以
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
tmp=[]
cur_len= max_len =0
if len(s)==0:return 0
for i in range(len(s)):
if s[i] in tmp:
j=tmp.index(s[i])#求相同字符s[i]在tmp中的index
tmp=tmp[j+1:] #移位，将list更新为最新的子字符串
cur_len-=j #更新子字符串长度
else:
cur_len+=1
tmp.append(s[i])
max_len=max(cur_len,max_len)
return max_len
执行用时 :76 ms, 在所有 Python 提交中击败了46.05%的用户
内存消耗 :13.6 MB, 在所有 Python 提交中击败了6.06%的用户
方法三：
怎么才能节省时间呢？
方法一用了str，方法二用了array，那么用dic 会怎样？
思路：下面的方式通过dic 标记相同元素位置，相同元素出现前获取当前片段最大长度，出现相同元素时，理解成区间截取，截取出现相同元素index之前的区间部分肯定没有上一次的长度长，这部分可以舍弃，所以只需要记录出现相同元素后的index 位置在继续遍历，最后取长度最大值即可。
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# 可抛弃字符串的索引尾值 - 字符串索引值，该索引值以及之前的字符都属于重复字符串中的一部分，不再在计算中涉及
ignore_str_index_end = -1
dic = {} # 任意字符最后出现在索引的位置 - {字符: 字符索引值}
max_length = 0 # 最长字符串长度
for i, c in enumerate(s):
# 如果字典中已经存在字符c，则字符c重复
# 如果字符索引值大于ignore_str_index_end，则字符c在需处理的范围内（补充说明请参考备注一）
if c in dic and dic[c] > ignore_str_index_end:
# 先更新可抛弃字符串的索引尾值为字符c上一次的索引值
ignore_str_index_end = dic[c]
# 再更新字符c的索引值
dic[c] = i
# 否则，
else:
# 更新字符最近的索引位置
dic[c] = i
# 更新最大长度
max_length = max(i - ignore_str_index_end, max_length)
return max_length
执行用时 :72 ms, 在所有 Python 提交中击败了49.95%的用户
内存消耗 :13 MB, 在所有 Python 提交中击败了6.06%的用户
时间方面还是很长，放弃～。～重在理解算法思路。