字符串的子串求解类问题是一整个系列的方法，正好用这道题作为我个人学习的一个总结吧。
作为一个没有训练过特定解法的新手，能够想到的最直观方法应该就是暴力求解法，这个方法时间复杂度必然很高，但是好在思路清晰，也容易上手，所以就先从暴力法开始吧。
题目描述：
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
暴力求解法
-
我的初始思路：
维护一个子串sub_string，外层循环按照给定字符串s每一个字符顺序扫描，并且和子串每一个字符进行比较（这里子串扫描应该从后往前），一旦当前字符在子串中找到相同的字符，那么子串就从相同字符前一个那里截断，然后把新字符加在结尾。每轮扫描后更新最长子串的长度，循环结束后返回。 -
代码：
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
sub_string = ''
lens = 0
for i in range(len(s)):
if sub_string:
for j in range(len(sub_string)-1,-1,-1):
if s[i] == sub_string[j]:
sub_string = sub_string[j+1:]
break
sub_string+=s[i]
#print(sub_string)
lens = max(lens, len(sub_string))
return lens
- 结果：
因为两层嵌套循环的使用，结果时间复杂度约为O（n^2），那么速度也是可想而知的慢……（还好没超时）
执行用时 :372 ms, 在所有 python3 提交中击败了13.76%的用户
我这个速度是注定要被人嘲笑的（还好我脸皮厚），接下来就是进阶之路啦。
暴力求解法的进化思路 -- 滑块法
- 思路：
我在网上偶然发现了一个跟我的思路非常像，但是效率高了很多的解法。来自于简书冬小羊的这篇博客，可以去读一下。
这个解法优化的点在于：
- 不需要维护一个子串了，而采用哈希表的方式记录每一个字符出现的次数，这样就可以很方便的找到多余的字符。
-
同时也就不需要遍历子串找到截断点。而是采用双指针指向子串首尾的方式，一旦子串里有字符重复，那么就移动子串头一格，直到子串里没有重复字符为止。其实这一步做的事情就相当于截断子串了。
下面这张图也来自于冬小羊的博客，大家可以直观感受一下这个解法：
滑动法图解
- 代码：
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
start = 0 # 子串起点指针
end = 0 # 子串终点指针
char_dict = dict() #统计子串中每一个字符出现的个数
lens = 0
for i in s:
end += 1
char_dict[i] = char_dict.get(i,0)+1
while char_dict[i] > 1:
char_dict[s[start]] -= 1
start += 1
lens = max(lens,end-start)
return lens
- 结果：
不得不说，这样修改之后，效果真的是杠杠的
执行用时 :80 ms, 在所有 python3 提交中击败了78.88%的用户
因为这样其实只有一个循环，内层因为巧妙使用指针和哈希表（就是字典表）所以大大提升了运行效率，感谢网友朋友们的智慧。
网友评论