LeetCode 第三题--无重复字符的最长子串

古城微笑少年丶 2021-11-12 00:10 236阅读 0赞

1. 题目

2.题目分析与思路

3.思路

### 1. 题目 ###

输入: "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

### 2. 思路 ###

从文中我们可以知道，最长的无重复字符，我们因该很自然的想到用字典，但是字典是无序的，所以我们必须稍微改变那么一点点。所以我的思路便是维护两个列表list1和result。 list1是动态的，表示的是当前最大的无重复的数组，如果我们判断下一个字符temp不在list1 中，那么我们就将其加入到list1中，否则的话，我们就要更新我们的list1.

如何更新呢，首先我们先找到list1中与temp相同的位置，我们将list1 变为temp到最后一位，同时将temp加入到list中。例如

$$list1=\[1,2,3,4\],temp = 3$$,那么list1就更新为$\[4，3\]$,通过这种手段，我们就发现list1 永远都是最优的结果。但是，这时一个问题就来了，list可能会变小，因此我们需要存储最长的list1 到result里面，整体思路就是这个样子。

### 3. 代码 ###

思路有了代码就很快出来了，这里我要说的是就是我们在改变list1的时候，一定要把temp加上，不然我们就会少一个字母。

def lengthOfLongestSubstring(s):
        length = len(s)
    #我们要维护的就是list1 与result
        list1 = []
        result = []
        for i in range(length):
            if s[i] not in list1:#如果temp不在list1中
                list1.append(s[i])
                if len(result) < len(list1):
                    #如果list1 长度小于result，则不改变result
                    result = list1
            else:  #修改list1
                list1 = list1[list1.index(s[i])+1:]
                list1.append(s[i])return len(result)

接下来的一章我就会将这种类似的题目全部做完，主要使用的是这个方法的扩展，划窗法去解决类似的问题。

30. 串联所有单词的子串

76. 最小覆盖子串

159. 至多包含两个不同字符的最长子串

209. 长度最小的子数组

239. 滑动窗口最大值

567. 字符串的排列

632. 最小区间

727. 最小窗口子序列

转载于:https://www.cnblogs.com/tjpeng/p/11245656.html