【完虐算法系列】「字符串 – 滑动窗口」复盘总结 (5)

③ left=0, right=2, 加入新元素 'c'，words={'a':0, 'b':1, 'c':2}, 窗口长度为3

④ left=0, right=3, 加入新元素 'a';

发现 a 已经在 words={'a':0, 'b':1, 'c':2} 存在；

则更新 left=max(words.get('a') + 1, left)=1，words={'a':3, 'b':1, 'c':2}

窗口长度为3

⑤ left=1, right=4, 加入新元素 'b';

发现 'b' 已经在 words={'a':3, 'b':1, 'c':2} 存在；

则更新 left=max(words.get('b') + 1, left)=2，words={'a':3, 'b':4, 'c':2}

窗口长度为3

⑥ left=2, right=5, 加入新元素 'c';

发现 'c' 已经在 words={'a':3, 'b':4, 'c':2} 存在；

则更新 left=max(words.get('c') + 1, left)=3，words={'a':3, 'b':4, 'c':5}

窗口长度为3

⑦ left=3, right=6, 加入新元素 'b';

发现 b 已经在 words={'a':3, 'b':4, 'c':5} 存在；

则更新 left=max(words.get('b') + 1, left)=5，words={'a':3, 'b':6, 'c':5}

窗口长度为2

⑧ left=5, right=7, 加入新元素 'b';

发现 'b' 已经在 words={'a':3, 'b':6, 'c':5} 存在；

则更新 left=max(words.get('b') + 1, left)=7，words={'a':3, 'b':7, 'c':5}

窗口长度为1

左右步骤描述完毕！

根据每一步骤记录的窗口长度，可得到最长窗口为 3。

下面就由上述逻辑得到最终的代码：

class Solution(object): def lengthOfLongestSubstring(self, s): if not s: return 0 left, right = 0, 0 length = 1 words = {} for right, v in enumerate(s): if s[right] in words.keys(): print(words.get(v) + 1, left) left = max(words.get(v) + 1, left) length = max(right-left+1, length) # 将当前值的 value 值覆盖 words[v] = right print(words) return length

</https:></https:>