题目： 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:
输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:
输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。解题思路： 可以使用滑动窗口来求解，有三种方法 方法1： 使用数组（容器），直观的滑动窗口法 设置滑动窗口数组，将遍历过的字符串储存在数组中，如果下一个遍历的字符不在窗口中则直接扩展窗口，如果在窗口中则移除字符及之前的字符串部分，然后再扩展窗口
class Solution(object): def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ if not s : return 0 window=[] #滑动窗口数组 max_length=0 #最长串长度 #遍历字符串 for c in s: if c not in window:#c不在滑动窗口中 window.append(c)#扩展c至滑动窗口 else:#字符串在滑动窗口中 window[:]=window[window.index(c)+1:]#从窗口移除重复字符及之前的字符串部分，新字符串即无重复字符的字符串 window.append(c)#扩展窗口 max_length=max(len(window),max_length) return max_length if max_length!=0 else len(s)方法2： 优化滑动窗口，使用双指针，记录滑动窗口起始和结束的索引值，可以减除数组的增删操作，提高效率。使用数组索引，标记滑动窗口
class Solution(object): def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ if not s : return 0 max_length=0 #最长串长度 left,right=0,0 #双指针 for i,c in enumerate(s): if c not in s[left:right]:#如果字符不在滑动窗口中，则直接扩展窗口 right+=1 #如果字符在滑动窗口中，则： #1.从窗口中移除重复字符及之前的字符串部分 #2.再扩展窗口 else: #在滑动窗口范围内查找对应的首个字符的索引X，对应新的左指针位置为X+1 #左指针右移，索引X增加一位 left+=s[left:right].index(c)+1 #右指针右移一位 right+=1 max_length=max(right-left+1,max_length) #如果最大长度不为零，返回最大长度 #如果最大长度仍为零，则说明遍历整个字符串都没有发现重复字符 return max_length if max_length !=0 else len(s)方法3： 使用Hash（字典），使用字典记录任意字符最近的索引值，字典查询时间复杂度为O（1），相比数组查询，效率更高 难点：理解什么是 可抛弃字符串的索引尾值，以及为什么需要dic[c]>start的判断
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] dic[c]=i else: #更新字符最近的索引位置 dic[c]=i #更新最大长度 max_length=max(i-ignore_str_index_end,max_length) return max_length备注一： 假设有字符串"abbcda", 观察可知最长不重复子串为"bcda" 根据编写的算法，在刚遍历至最后一个’a’时，dic[‘a’]的值为0，此时ignore_str_index_end的值已经更新为索引1，索引1以及之前的字符都是出现在重复字符之前，不用再在运算中考虑的字符。 ignore_str_index_end的注释，是可抛弃字符串的索引尾值，是双指针方法中左指针（起始针）的反面; 如果仍然不好理解，可以做到理解双指针法也行，毕竟ignore_str_index_end的确有点绕…
今天的算法题依旧很困难，仍然是参考了其他人的思路，以前的编程基础太差，还需继续加油
