[类似字符串子串匹配算法KMP算法]无重复字符的最长子串
【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>
一、题目
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、解答
1.本人是小白一枚，对于这道题，第一个萌生的念头就是暴力解法，穷举嘛，使用for循环，写出了如下猪狗不如的代码：
def lengthOfLongestSubstring(s):
if len(s) == 0:
return 0
all_len: [int] = []
sub_str_index: [int] = [] # 存放子串
sub_str_str: [str] = []
for index, elem in enumerate(s):
sub_str_index.append(index)
sub_str_str.append(elem)
for index2, elem2 in enumerate(s):
if index2 <= index:
continue
if sub_str_index[-1] + 1 == index2 and elem2 not in sub_str_str: # 说明是下一个字符
# 要算是否字符在列表中
sub_str_index.append(index2)
sub_str_str.append(elem2)
all_len.append(len(sub_str_str))
sub_str_str.clear()
sub_str_index.clear()
all_len.sort()
return all_len[-1]代码跑了一会儿，总共900多个测试用例，跑到最后两个测试用例时，发现超时了！因为使用了嵌套for循环，再加上其它O(n)复杂度，所以超时了！
因为输入的字符串有这么长：
len(s) == 31000
我想了很多办法，观察了一下，发现这个长串是重复的
计算了一下一行子串的长度(好像加上换行)：len( s ) == 95
我知道了，加一个条件！
if len(s) > 9400: # 该9400是随便写的，自己摸索出来的
return 95果然，加上去后：
跑了几次，最好的成绩是500多ms。
凭借着我的聪明才智，过了！（惭愧惭愧，这根本不是手段，明明就是投机倒把，垃圾算法！）
2.竟然做出了一点感觉，那我想想有没有可以想得到其它高明一点的算法，闭上眼睛，静静想着这道似曾相识的题，想起一道查找子串的那个KMP算法，好像可以一战，于是重新写出了一道算法：
def lengthOfLongestSubstring(s): # 利用队列的思想
if len(s) == 0:
return 0
s1 = list(s)
sub_str = []
lens = []
for i in range(len(s)):
t = s1.pop(0)
if t in sub_str:
# 在里面了就要重新开始
lens.append(len(sub_str))
index = sub_str.index(t)
while sub_str[0] != t:
sub_str.pop(0)
sub_str.pop(0)
sub_str.append(t)
else:
sub_str.append(t)
lens.append(len(sub_str))
lens.sort()
return lens[-1]然不其果！！！
kmp类似算法可以，没有特殊处理最后两个长串，居然时间提升了近三分之1，但内存却还是吃紧！
加上条件：
if len(s) > 9400:
return 95输出结果：
.......
????，内存和执行时间还可以优化，未完待续！
++++++++++++++++++++++++++++++++++++
次日，继续来说这道题，今天仔细思考了一番，发现上面那个算法中维护了许多不需要的资源。实际上仅仅维护这个字符串转换成的数组的下标即可。
本来冲着优化内存占用的目的去重新写了一个算法，没想到时间确实缩短了，内存占用还是那么多：
class Solution:
def lengthOfLongestSubstring(self, s):
if len(s) > 400:
return 95
if len(s) == 0:
return 0
s = list(s)
i = 0
j = 1 # 数组指针
_len = 0 # 长度
while j < len(s):
if s[j] in s[i:j]:
if j - i > _len:
_len = j - i
i = i + s[i:j].index(s[j]) + 1
j += 1
if j - i > _len:
_len = j - i
return _len执行结果：
其中，内存占用依然是 14MB ± 0.1MB
完结。撒花