Leetcode（3）无重复字符的最长子串

[题目表述]：

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

第一种方法：暴力

执行用时：996 ms； 内存消耗：12.9MB 效果：太差

class Solution(object):

    def lengthOfLongestSubstring(self, s):

        """

        :type s: str

        :rtype: int

        """

        Maxsize=0

        res=''

        if len(s)==1:Maxsize=1

        for i in range(len(s)):

            for j in s[i:len(s)]:

                if j not in res:res+=j

                else:

                    break

                Maxsize=max(Maxsize,len(res))

            res=''

        return Maxsize

学习

• 利用一个空串来存储子串

• for对迭代对象的使用

第二种方法：一个for加切片操作

执行用时：60 ms； 内存消耗：12.1MB 效果：非常好

class Solution:

    def lengthOfLongestSubstring(self, s):

        """

        :type s: str

        :rtype: int

        """

        res = ''

        maxlen = 0

        for i in s:

            if i not in res:

                res += i

            else:

                maxlen = max(maxlen, len(res))

                index = res.index(i)

                res = res[index + 1:] + i

        return max(maxlen, len(res))

学习

• 算法有点类似于字符串匹配模式算法KMP

• 出现重复的移动到重复字符的后一个位置，截取之后继续操作

• 就不用for+for，只需要用一个for，跟改进匹配算法一样的改进方式

• 字符串可以+= + 这种重载运算符

• 切片
  
  • [:] 提取从开头（默认位置0）到结尾（默认位置-1）的整个字符串

  • [start:] 从start 提取到结尾

  • [:end] 从开头提取到end - 1

  • [start:end] 从start 提取到end - 1

  • [start