小说做任务赚钱的网站/广西网络优化seo

无重复最长字符串

假设原始字符串S如下

从左侧开始遍历S，以i标记窗口左侧，j标记窗口右侧，初始时，i=0，j=0，即开头a所在的位置，此时，窗口大小为1。然后，将j右移，逐步扩大窗口，依次经过b、c、d，此时，窗口内均无重复字符，继续右移j

当j移动到d后面的a所在位置时，对应字符a在窗口中已存在，此时，窗口大小为5，去除当前重复的一位，窗口大小为4。此时窗口内的字符串abcd为

找到窗口中已存在的该字符所在位置，并将i移动到该位置下一位置

此时为第二个窗口

继续重复之前的操作，直到j移动到字符串最后一位停止。

示例代码
class Solution:def lengthOfLongestSubstring(self, s: str) -> int:# 如果字符串s为空，返回0if not s:return 0# 保存窗口内字符串lookup = list()n = len(s)# 最大子串长度max_len = 0# 当前窗口长度cur_len = 0# 遍历字符串sfor i in range(n):val = s[i]# 如果该值不在窗口中if not val in lookup:# 添加到窗口内lookup.append(val)# 当前长度+1cur_len+=1# 如果该值在窗口中已存在else:# 获取其在窗口中的位置# 需要注意的是，index求的是所求字符的第一个字符index = lookup.index(val)# 移除该位置及之前的字符，相当于上图中的图3到图4# 这样可以将窗口中重复的字符去掉，得到b,c,dlookup = lookup[index+1:]# 再将重复的字符a放到窗口中lookup.append(val)# 当前长度更新为窗口长度，cur_len = len(lookup)# 如果当前长度大于最大长度，更新最大长度值if cur_len > max_len:max_len = cur_len# 返回最大子串长度return max_len

特别需要注意的地方就是：
在原有的程序中没有提到这一点，在这里我补充一下，
利用index求去字符的索引时，只求取第一个字符的索引。
程序参考地址：

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-dong-chuang-kou-tu-wen-jiang-jie-by-superychen/