python实现最长不重复连续字符长度(DP)
实现思路
方法:双指针 + sliding window
- 定义两个指针 start 和 end 得到 sliding window
- start 初始为 0,用 end 线性遍历每个字符,用 recod 记录下每个字母最新出现的下标
两种情况:一种是新字符没有在 record 中出现过,表示没有重复,一种是新字符 char 在 record 中
出现过,说明 start 需要更新,取 start 和 record[char]+1 中的最大值作为新的 start。
**需要注意的是:两种情况都要对 record 进行更新,因为是新字符没在 record 出现过的时候需要添加
到 record 中,而对于出现过的情况,也需要把 record 中对应的 value 值更新为新的**
示例代码
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
record = {}
start,res = 0,0
for end in range(len(s)):
if s[end] in record:
start = max(start, record[s[end]] + 1)
record[s[end]] = end
res = max(res, end - start + 1)
return res
时间复杂度:O(n)
空间复杂度:O(1)
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。