leetcode-3.-无重复字符的最长子串及输出最长子串的长度 位置 子串

• 方法一：暴力求解 会超时

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        tmp_dict = {'max_str':'','start_index':0,'max_lenght':0}
        n = len(s)
        for i in range(n):
            tmp_str = s[i]
            for j in range(i+1,n):
                if s[j] not in tmp_str:
                    tmp_str +=s[j]
                else:
                    break
            lenght = len(tmp_str)
            if lenght > tmp_dict['max_lenght']:
                tmp_dict = {'max_str':tmp_str,'start_index':i,'max_lenght':lenght}
        return tmp_dict['max_lenght']
       

方法二：使用滑动窗口优化，执行时间50ms,推荐此方法，重点理解滑动窗口的用法与Python内置方法的时间复杂度

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        left = 0
        lookup = set()
        n = len(s)
        max_len = 0
        cur_len = 0
        for i in range(n):
            cur_len += 1
            # 集合中的in操作平均时间复杂度为O(1),而列表为O(n)
            while s[i] in lookup:
                lookup.remove(s[left])
                left += 1
                cur_len -= 1
            if cur_len > max_len:
                max_len = cur_len
            lookup.add(s[i])
        return max_len

Python内置方法的时间复杂度参考网址

• Python内置方法的时间复杂度