《高性能网站建设指南百度快照替代

Problem: 3. 无重复字符的最长子串

思路

一上来马上想到两层for循环暴力枚举，但是又立马想到复杂度是$O(n^2)$，思考了一下能否有更优解，于是想到用头尾两个指针来指定滑动窗口（主要是python的字符串可作为字符列表来操作，用头尾两个指针的列表索引来提取子串很方便）

解题方法

1、首先考虑特殊情况，字符串长度为0或为1，则直接返回字符串长度num_char
2、设置一个变量max_son来记录最长子串长度
3、设立头尾两个指针i、j，初始值都为0，用来提取子串以滑动窗口
4、当j指向的下一个字符不在目前的子串中，即可以形成新的不重复子串，则j+1，且如果超过最大子串长度，则更新max_son的值
5、当j指向的下一个字符出现重复，则i+1，用新的头指针来遍历
6、直到j到达字符串末端，则停止

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(n)$

Code

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:num_char = len(s)if num_char <= 1:return num_charmax_son = 1i, j = 0, 0while j < num_char-1:str_son = s[i:j+1]if s[j+1] not in str_son:if len(str_son)+1 > max_son:max_son = len(str_son)+1j += 1else:i += 1j = ireturn max_son