[已解决]无重复字符的最长子串

杨扬阳羊洋

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例：
输入:"pwwkew"
输出:3
解释：因为无重复字符的最长子串是“wke”，所以其长度为3

最佳答案

月排行榜 / 总排行榜

Stubborn

2019-4-5 22:53:21

历遍字符串，把正在历遍的元素添加到一个列表，下一次历遍的时候，这边元素不在列表，继续添加，在的话，求出当前列表的个数，添加到新的列表（长度），清空列表，然后循环添加判断，历遍完毕，返回列表的最大值，昨天不是问过了吗？

1. def string(str):
   
2.     str_list=[]
   
3.     str_len=[]
   
4.     for i in str:
   
5.         if i not in str_list:
   
6.             str_list.append(i)
   
7.         else:
   
8.             str_len.append(len(str_list))
   
9.             str_list = []
   
10.             str_list.append(i)
    
11.     return max(str_len)

复制代码

跳转到最佳答案楼层

TOP_LK

因为找的是无重复的子串，因此使用集合set来存放已经找到的字符，set中保存的是从某个位置pre到另一个位置i中间的所有字符。

从头开始遍历给定的字符串s, 每遍历一个，判断set中是否有该字符，假设此时遍历到i位置：

1： 如果没有，就将字符加入set, 表明子串的长度又增大了一个，即prev~i位置的字符串是无重复字符的，更新最长字串的长度max_len;

2： 如果有，就从prev位置开始循环遍历，直到找到与i位置字符相等的那个字符，然后prev指向那个字符位置+1的位置，i继续遍历。

直到i==len结束遍历。但此时还应该计算一次max_len=Max(i-prev, max_len)，返回最终的max_len

Stubborn

历遍字符串，把正在历遍的元素添加到一个列表，下一次历遍的时候，这边元素不在列表，继续添加，在的话，求出当前列表的个数，添加到新的列表（长度），清空列表，然后循环添加判断，历遍完毕，返回列表的最大值，昨天不是问过了吗？

1. def string(str):
   
2.     str_list=[]
   
3.     str_len=[]
   
4.     for i in str:
   
5.         if i not in str_list:
   
6.             str_list.append(i)
   
7.         else:
   
8.             str_len.append(len(str_list))
   
9.             str_list = []
   
10.             str_list.append(i)
    
11.     return max(str_len)

复制代码

杨扬阳羊洋

Stubborn 发表于 2019-4-5 22:53
历遍字符串，把正在历遍的元素添加到一个列表，下一次历遍的时候，这边元素不在列表，继续添加，在的话，求 ...

哈啊，思路有点闭塞，想不出怎么做