每日leetcode——3. 无重复字符的最长子串数据结构与算法

题目给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

暴力枚举 【每日leetcode——3. 无重复字符的最长子串】思路一：以每个字符为开始，遍历字符串，用一个字典保存遍历的字符，遇到重复的就结束，用一个数组保存本次无重复子串的长度，返回最大的

def lengthOfLongestSubstring(s): if not s: return 0slen = [1] * len(s) for i in range(0,len(s)): hashTable = {} hashTable[s[i]]=1 for j in range(i+1, len(s)): if s[j] in hashTable: break else: hashTable[s[j]]=1 slen[i]+=1 return max(slen)

滑动窗口

# 思路二：滑动窗口 # 定义两个指针，i和j，i作为无重复子串的开头，j作为无重复子串的结尾 # 定义一个字典st，用来保存每个字符的最后一次出现的位置 # 定义一个ans变量，用来保存最长无重复子串的长度 # 初始时，i,j=0，都在开头位置 # 随着for循环遍历字符，j不断向后移动 # 在j移动的过程中，如果当前字符在st中已经存在了，说明之前的字符中存在相同的字符，这段无重复子串到此就结束了，需要移动i来调整窗口 # 移动i时需要注意： # 在移动前，如果i的位置<=重复字符的最新位置（..[i..重复字符..j]..)， # 说明重复字符就在当前窗口中，需要将i移动到重复字符的下一个位置(..重复字符[i..j]..) # 如果i的位置>重复字符的最新位置 (..重复字符..[i..j]..)， # 说明重复字符在当前窗口前面，并不在当前窗口中，当前窗口的子串是无重复的，则i保持不动， # i和j的位置都确定好后，再更新ans，ans=Max(ans, j-i+1)，当前的长度和之前的长度比较，选最大的，让ans保存的是最大长度 # 最后将{当前字符:出现的位值}保存在字典st中def lengthOfLongestSubstring(s): st = {} i, ans = 0, 0 for j in range(len(s)): if s[j] in st: i = max(i, st[s[j]]+1) ans = max(ans,j-i+1) st[s[j]] = j return ans;