Leetcode3. 无重复字符的最长子串 Python实现
文章目录
- 题目要求:

思路
- 用一个字典来存数组元素的index
- 记录一个start,用来表示当前的不重复的字符串的起点
- 定义mymax,保存当前遍历过的最长的字符串的长度
- 遍历数组,如果元素i不在字典中,说明当前没有出现重复的字符,如果i的下标-start大于mymax,也就是当前不重复的字符串的长度大于保存的最长的长度,更新mymax的值,如果元素i在字典中,说明前面已经有重复的元素,把字典中mymax[i]的值赋给start,更新mymax[i]为当前的下标。比如字符串abhwb,遍历到第二个b时,当前不重复的字符串是从上一次出现的b的下一位到当前的b,所以要先把mymax[i]的值赋给start。
- 核心代码:
mydict = {}
mymax = 0
# start从-1开始是因为有一个特殊的测试用例" ",需要返回的值是1
start = -1
for i in range(len(s)):
# 如果遍历到的元素在字典中,说明重复出现了,而且如果这个值上一次出现的位置在start后面,start需要更新
if s[i] in mydict and mydict[s[i]] > start:
#字典中旧的值赋给start,即上一次该元素出现的位置,更新字典中这个元素当前的位置
start , mydict[s[i]] = mydict[s[i]] , i
else:
#如果不在字典中,把这个值加到字典里,value为该元素的下标
mydict[s[i]] = i
# i - start为当前无重复的字符串的长度,如果这个长度比记录的最长的值mymax还大,更新mymax
if i - start > mymax:
mymax = i - start
return mymax- 完整代码:
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
mydict = {}
mymax = 0
start = -1
for i in range(len(s)):
if s[i] in mydict and mydict[s[i]] > start:
start , mydict[s[i]] = mydict[s[i]] , i
else:
mydict[s[i]] = i
if i - start > mymax:
mymax = i - start
return mymax
解释2:
- 用一个字典来保存所有遍历过的字符及字符出现的下标,一个start用来标识当前不重复子串起点的前一个位置,一个res用来表示结果(子串的最大长度)
- 从头开始遍历这个字符串,如果遇到不在字典中的字符,就把这个字符及下标记录到字典中,如果当前的index-start,也就是不重复子串的长度比res大,那么把当前不重复子串的长度赋给res
- 如果遇到在字典中的字符,且这个字符上一次出现的下标大于start的当前位置,那么把这个位置赋给start(也就是start只向后移动),再把字典里的这个字符对应的下标更新
- 最后返回结果res
- 核心代码
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# start标志不重复子串的前一个位置
start = -1
# 字典,用来保存字符及字符上一次出现的下标
d = {}
# 不重复子串的最大长度
res = 0
# 遍历字符串
for i in range(len(s)):
# 字符在字典中,且start不往回走
if s[i] in d and d[s[i]] > start:
start = d[s[i]]
d[s[i]] = i
# 字符不在字典中
else:
d[s[i]] = i
# 也可以写成 res = max(res, i - start)
if i - start > res:
res = i - start
return res- 完整代码:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
start = -1
d = {}
res = 0
for i in range(len(s)):
if s[i] in d and d[s[i]] > start:
start = d[s[i]]
d[s[i]] = i
else:
d[s[i]] = i
if i - start > res:
res = i - start
return res
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论