给一个公司做网站维护,线下推广方案,深圳设计装修公司,承德网站设计公司Problem: 3. 无重复字符的最长子串 文章目录 思路解题方法复杂度Code 思路 一上来马上想到两层for循环暴力枚举#xff0c;但是又立马想到复杂度是 O ( n 2 ) O(n^2) O(n2)#xff0c;思考了一下能否有更优解#xff0c;于是想到用头尾两个指针来指定滑动窗口#xff08;主… Problem: 3. 无重复字符的最长子串 文章目录 思路解题方法复杂度Code 思路 一上来马上想到两层for循环暴力枚举但是又立马想到复杂度是 O ( n 2 ) O(n^2) O(n2)思考了一下能否有更优解于是想到用头尾两个指针来指定滑动窗口主要是python的字符串可作为字符列表来操作用头尾两个指针的列表索引来提取子串很方便 解题方法 1、首先考虑特殊情况字符串长度为0或为1则直接返回字符串长度num_char 2、设置一个变量max_son来记录最长子串长度 3、设立头尾两个指针i、j初始值都为0用来提取子串以滑动窗口 4、当j指向的下一个字符不在目前的子串中即可以形成新的不重复子串则j1且如果超过最大子串长度则更新max_son的值 5、当j指向的下一个字符出现重复则i1用新的头指针来遍历 6、直到j到达字符串末端则停止 复杂度
时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( n ) 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:j1]if s[j1] not in str_son:if len(str_son)1 max_son:max_son len(str_son)1j 1else:i 1j ireturn max_son
