给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
这道题,一开始最直接的想法就是暴力法,直接穷举所有的子串,然后选择无重复的子串中最长的那个。
方法如下:
# 暴力法,会超时
def lengthOfLongestSubstring(s):
maxlen=0
for i in range(len(s)):
for j in range(len(s)-i+1):
j = j+i
if (len(s[i:j])==len(set(s[i:j]))) & (len(s[i:j])>maxlen): maxlen=len(s[i:j])
return maxlen
可惜,事情往往没有那么简单,超时了,简单分析下来,这个时间复杂度达O(n^2),所以,看起来应该是有更优的算法来解决。
先思考一下,后面我会给出一个解题思路~?
图来自网络
下面介绍一种"滑动窗口"的解题思路
1 )定义一个空的集合Lookup(集合的元素是唯一的)
2 )滑动窗口cur_len 一开始的长度为1,并且从字符串s最左端开始向右滑动(滑动N次,N为字符串s的长度),滑动窗口cur_len加长1
3 )每次判断右端元素s[i]是否存在于集合Lookup中,如何不存在,则集合Lookup添加上这个元素,并且判断当前窗口长度cur_len是否大于max_len,是的话就更新max_len
4 )但如果右端元素s[i]存在于集合Lookup中,则移除集合Lookup最左端的元素Lookup[left],并且left加1,滑动窗口cur_len减1
5 )再次判断右端元素s[i]存在于集合Lookup中,如果是的话,重复步骤4),直到右端元素s[i]不存在于集合Lookup中,然后判断当前窗口长度cur_len是否大于max_len,是的话就更新max_len
6 )循环回步骤2),直到字符串s的最右端,返回max_len。
Python实现:
# 滑动窗口
@pysnooper.snoop()
def lengthOfLongestSubstring( s: str) -> int:
if not s:return 0
left = 0
lookup = set()
n = len(s)
max_len = 0
cur_len = 0
for i in range(n):
cur_len += 1
while s[i] in lookup:
lookup.remove(s[left])
left += 1
cur_len -= 1
if cur_len > max_len:max_len = cur_len
lookup.add(s[i])
return max_len
? 配图角色背景介绍:
战争机器(War Machine)是美国漫威漫画旗下超级英雄,初次登场于《钢铁侠》(Iron Man)第118期(1979年1月)。本名詹姆斯·罗德斯(James Rhodes),是钢铁侠托尼·史塔克的好友、一名美军上校,也是美国陆军武器开发部的部长,还是斯塔克工业与美国军队的中间人,因一次敌人来袭,钢铁侠不敌,在万分危急的时刻,詹姆斯穿上了钢铁侠的另一套高科技装甲,与其一同将敌人击退,因此托尼将此装甲送给了他,后詹姆斯在美国政府的协助下将此装甲的攻击系统加以改进,并穿上了它,从此化身战争机器,与钢铁侠并肩作战,后加入复仇者联盟。