题目内容

描述

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

示例：

给定 “abcabcbb” ，没有重复字符的最长子串是 “abc” ，那么长度就是3。

给定 “bbbbb” ，最长的子串就是 “b” ，长度是1。

给定 “pwwkew” ，最长子串是 “wke” ，长度是3。请注意答案必须是一个子串，”pwke” 是子序列而不是子串。

思路 1——暴力求解

粗略的想法就是，把字符串的所有子串全部试探一遍，如果有重复的字符，那么就舍弃这个子串；然后取所有子串中满足条件最长的那个。然鹅，这样超时了。简单分析一下，一个长度为n的字符串所有的子串个数为$n+(n-1)+(n-2)+…+3+2+1=\frac{(n+1)*n}{2}=\frac{(n^2+n)}{2}$，再加上对每个子串判断是否有重复，所以整体的时间复杂度应该是O(n^3)。代码如下

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        n=len(s)
        if n<=1:
            return n

        maxLen=1
        for i in range(n):
            for j in range(i+1,n):
                str=s[i:j+1]
                if self.noRepeatCharacter(str)==True:
                    maxLen=max(j-i+1,maxLen)


        return maxLen

    # 判断一个字符串是否含有重复的字母
    def noRepeatCharacter(self, s):
        charSet=set()
        for ch in s:
            if ch in charSet:
                return False
            else:
                charSet.add(ch)
        return True

说明一下：在提交的时候case中有“”和“ ”,我也懒得处理特殊情况下i和j要不要加1什么的，直接单列出这两个特殊情况

思路 2 ——“双指针”窗口移动思想

在暴力法中，我们会反复检查一个子字符串是否含有有重复的字符，但这是没有必要的。如果从索引 $i$到 $j−1 $之间的子字符串$ s{ij}$已经被检查为没有重复字符。我们只需要检查 $s[j]$对应的字符是否已经存在于子字符串$ s{ij}$ 中。

主要的思想其实和思路1类似，只不过找子串的方式有点变化。现在是以索引$i$为头，一直去找最长的那个子串。

如果$j$对应的字符没出现过，则追加到当前寻找的字符串上；
如果$j$对应的字符在集合中出现过，那么就移动$i$，同时在集合中把索引$i$对应的字符逐个删去，直到集合中$j$对应的字符没出现过。（目的就是找到，另一个以索引$i’$为头,它的最长不重复子串，从而找到所有这样的以$i’$为头的子串中最长的那个） 这句话有点绕，配合代码看一下就明白了

class Solution:
    def lengthOfLongestSubstring(self, s):
        charSet=set()
        n=len(s)
        if n<=1:
            return n
        maxLen=1
        i=0
        j=0
        while(i<n and j<n):
            # 如果集合中不存在当前字符
            if s[j] not in charSet:
                charSet.add(s[j])
                j+=1
                maxLen = max(j - i, maxLen)
            else:
                charSet.remove(s[i])
                i+=1
        return maxLen

这样下来，不是移动i指针，就是移动j指针，最坏的情况就是i和j都从头移到了尾，也就是$2n$个子串，瞬间比原来的$n^2$减少了许多重复情况

要注意的地方

思路2中的maxLen = max(j - i, maxLen)语句，前一个参数不能是j-i+1，因为在这句之前们执行了j++操作。
在类定义中，如果涉及到成员函数之间的调用，可以采用以下两种方式：
1. 类名.函数名（self,…）
2. self.函数名（…）

LeetCode-3-最长不重复子串

题目内容

描述

示例：

思路 1——暴力求解

思路 2 ——“双指针”窗口移动思想

要注意的地方

FEATURED TAGS

FRIENDS