字节跳动2018.9.9笔试最长不重复子串

蔚落 2022-05-13 02:16 185阅读 0赞

# 题目描述 #

给定一个字符串，请找出其中无重复字符的最长子字符串的长度。例如，“abcabcbb”，其无重复字符的最长子字符串实“abc”，其长度为3。“bbbbb”，其无重复字符的最长子字符串是“b”，长度为1。  
此题是[leetcode第三题][leetcode]原题。

# 本人思路 #

![这里写图片描述][70]  
以上图为例，已经扫描到了abc了：  
如果循环到了字符a，与当前扫描到的字符串中的a重复了，那么新的字符串就应该从a之后开始到当前循环字符。  
如果循环到了字符b，与当前扫描到的字符串中的b重复了，那么新的字符串就应该从b之后开始到当前循环字符。  
…  
如果循环到了字符d，与当前扫描到的字符串中每个字符都不重复，那么新的字符串就应该从起始位置到当前循环字符。

# 代码 #

s = input()
    n = len(s)
    
    temp = []#存储当前扫描到的无重复最长子串
    maxleng = 0 
    
    for i in range(n):
        if(s[i] not in temp):#如果不在temp里就添加进去
            temp.append(s[i])
        else:#如果在里面，查看temp的长度是否比maxleng大
            if len(temp)>maxleng:
                maxleng = len(temp)
            index = temp.index(s[i])#获得当前重复的索引
            temp = temp[index+1:len(temp)]#新的temp是从重复字符之后开始
            temp.append(s[i])#再添加当前重复字符
    if len(temp)>maxleng:#计算最后一次
        maxleng = len(temp)
    print(maxleng)

但此代码有个弊端，就是需要temp数组来存当前扫描到的无重复子串，实际是不需要的。

# 最优思路 #

上LeetCode提交我的代码，运行时间124ms，打败了44%的人，可见我这个算法之差啊。但由于我提交的代码是python3，在LeetCode里面也只能看见python3里面的最优代码（80ms），下面我将对最优代码进行讲解。

class Solution:
        def lengthOfLongestSubstring(self, s):
            """ :type s: str :rtype: int """
            start, longest, store = 0, 0, {}
            for i, c in enumerate(s):
                if c not in store:
                    store[c] = i
                else:#当前c已经出现过了，但不一定在当前扫描到的无重复子串中
                    #记录下当前c之前位置扫描到无重复子串的长度
                    longest = max(longest, i - start)
                    #更新无重复子串的开始位置，为下一次记录作好准备
                    #如果当前c不在当前扫描到的无重复子串中，start不会更新
                    #因为这种情况下，store[c] + 1 <= start
                    start = max(start, store[c] + 1)
                    #更新每个字符的最新位置
                    store[c] = i
            longest = max(longest, len(s) - start)#记录最后一次
            return longest

此代码相比我的代码，优点在于不需要temp数组存储当前扫描到无重复子串，而是用start记录无重复子串的开始索引。

但是代码的思想和我的是很类似的。

和最优代码的进入else的条件不一样，我是在temp里有重复的就进入，所以无重复子串的起始位置肯定会更新；最优代码是只有字符是第二次出现就进入else，但不一定会更新无重复子串的起始位置。

`start`索引记录无重复子串的起码位置，`i`记录的是`i-1`是无重复子串的终止位置。我的代码中，是根据当前字符是否与temp有重复，如果有就进入else，进入else后起始位置start必更新。最优代码中，是根据当前字符是否出现过，如果出现过就进入else，进入else后起始位置start不一定更新，因为有可能当前字符上一次出现索引在start前面，这样的话start就不会更新。

start更新后，就为下一次进入else作好了准备，下一次执行`longest = max(longest, i - start)`，`i - start`则就是下一次扫描到的无重复子串的长度。

再分析终止位置吧，当循环变量到了`i`时，终止位置则为`I-1`，看我画的第一个图就能明白。

[leetcode]: https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
[70]: /images/20220513/ba226fcb1b2f43eda4247dffa84e9ee7.png