浏览量 4408
2011/03/03 01:55
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
思路：
这道题主要用到思路是：滑动窗口
什么是滑动窗口？
其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！
如何移动？
我们只要把队列的左边的元素移出就行了，直到满足题目要求！
一直维持这样的队列，找出队列出现最长的长度时候，求出解！
时间复杂度：O(n)O(n)
代码：
PythonC++Java
class Solution:
def lengthOfLongestSubstring(self, 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
下面介绍关于滑动窗口的万能模板,可以解决相关问题,相信一定可以对滑动窗口有一定了解!
模板虽好,还是少套为好!多思考!更重要!
还有类似题目有:
3. 无重复字符的最长子串
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
from collections import defaultdict
lookup = defaultdict(int)
start = 0
end = 0
max_len = 0
counter = 0
while end < len(s):
if lookup[s[end]] > 0:
counter += 1
lookup[s[end]] += 1
end += 1
while counter > 0:
if lookup[s[start]] > 1:
counter -= 1
lookup[s[start]] -= 1
start += 1
max_len = max(max_len, end - start)
return max_len
76. 最小覆盖子串
class Solution:
def minWindow(self, s: 'str', t: 'str') -> 'str':
from collections import defaultdict
lookup = defaultdict(int)
for c in t:
lookup[c] += 1
start = 0
end = 0
min_len = float("inf")
counter = len(t)
res = ""
while end < len(s):
if lookup[s[end]] > 0:
counter -= 1
lookup[s[end]] -= 1
end += 1
while counter == 0:
if min_len > end - start:
min_len = end - start
res = s[start:end]
if lookup[s[start]] == 0:
counter += 1
lookup[s[start]] += 1
start += 1
return res
159. 至多包含两个不同字符的最长子串
class Solution:
def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
from collections import defaultdict
lookup = defaultdict(int)
start = 0
end = 0
max_len = 0
counter = 0
while end < len(s):
if lookup[s[end]] == 0:
counter += 1
lookup[s[end]] += 1
end +=1
while counter > 2:
if lookup[s[start]] == 1:
counter -= 1
lookup[s[start]] -= 1
start += 1
max_len = max(max_len, end - start)
return max_len
340. 至多包含 K 个不同字符的最长子串
class Solution:
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
from collections import defaultdict
lookup = defaultdict(int)
start = 0
end = 0
max_len = 0
counter = 0
while end < len(s):
if lookup[s[end]] == 0:
counter += 1
lookup[s[end]] += 1
end += 1
while counter > k:
if lookup[s[start]] == 1:
counter -= 1
lookup[s[start]] -= 1
start += 1
max_len = max(max_len, end - start)
return max_len
滑动窗口题目:
3. 无重复字符的最长子串
30. 串联所有单词的子串
76. 最小覆盖子串
159. 至多包含两个不同字符的最长子串
209. 长度最小的子数组
239. 滑动窗口最大值
567. 字符串的排列
632. 最小区间
727. 最小窗口子序列
下一篇：无重复字符的最长子串 c++实现三种解法 多重循环，hashmap优化，桶优化
© 著作权归作者所有
75
条评论
最热
编辑
预览
评论
精选评论(2)
喵了个咪
7 个月前
不一定是左边的元素移除吧。。
46
踩
查看 12 条回复
回复
陈志伟
5 个月前
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size() == 0) return 0;
unordered_set<char> lookup;
int maxStr = 0;
int left = 0;
for(int i = 0; i < s.size(); i++){
while (lookup.find(s[i]) != lookup.end()){
lookup.erase(s[left]);
left ++;
}
maxStr = max(maxStr,i-left+1);
lookup.insert(s[i]);
}
return maxStr;
}
};
小菜鸡，刚开始刷力扣，很多东西不明白，基本都是看答案写的。针对003 无重复字符的最长字串，参考如上答案，C++版本。编者很辛苦，没有给出具体解释，我想说出自己的一些想法。
1.对于大多数人比较纠结的一点
while (lookup.find(s[i]) != lookup.end()){
lookup.erase(s[left]);
left ++;
}
这段代码结果是不断从左缩小窗口，直到窗口中不存在与下一个字符重复的字符。
lookup.find() 查找对应元素，成功返回对应的迭代器，失败返回最后一个元素迭代器（即 lookup.end() ）
lookup.end() 大多数人认为是最后添加进去的元素对应的迭代器，其实不然，是最后添加进去的元素对应的迭代器的下一个（最后一个元素对应的迭代器），此处有点绕，大家可以去找找相关资料，就很清晰了。
2.小白刚开始刷力扣，其实刷了三题，发现一个规律，最初的算法思想很多都是来自遍历过程。也就是所谓的暴力算法，但是由于哈希和一些高级数据结构的操作，实现了查询时间复杂度为常数的方法，进而衍生出优化方法（这是小白自我感觉，无论对错，希望得到老哥们的指点）
24
踩
回复
评论(75)
echooj
20 天前
为什么用set, 我尝试改变了成数组，依旧能够通过：
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:return 0
left = 0
lookup = []
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.append(s[i])
return max_len
作者：powcai
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-dong-chuang-kou-by-powcai/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。