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. 最小窗口子序列