- 难度：
中等 - 本题涉及算法：
滑动窗口 - 思路：
滑动窗口 - 类似题型:
题目 3. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释 : 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
方法一 滑动窗口
解题思路
- 这种数组类型题目很容易会想到通过
暴力去解决问题，当然可以，而且为新的方法提供思路 - 暴力解法时间复杂度较高，会达到 $O(n^2)$，所以我们借用空间
哈希表采取滑动窗口的方法降低时间复杂度 (借用空间降时间) - 通过
map记录元素及下标，同时通过left记录左边界 - 如图(新手，图做的不好)))
代码
python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
left = 0
len_max = 0
sub_dict = {}
sub_len = len(s)
for i in range(len(s)):
if s[i] in sub_dict:
len_max = max(len_max,i-left) # 当出现重复的元素，先判断最长子串的长度
left_curr = sub_dict.get(s[i]) + 1 # 记录零时的左边界
# 判断当前左边界和上一个左边界的大小 当前边界下雨上一个边界 则左边界不变
# 如 字符串 "abba"
left = left_curr if left_curr > left else left
sub_dict[s[i]] = i
return max(len_max,sub_len-left)
java
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer> map = new HashMap<>();
int max = 0;
int left = 0;
int len = s.length();
for(int i=0;i<s.length();i++) {
if (map.containsKey(s.charAt(i))) {
max = Math.max(max,i - left); // 当出现重复的元素，先判断最长子串的长度
int cur = map.get(s.charAt(i))+1; // 记录零时的左边界
// 判断当前左边界和上一个左边界的大小 当前边界下雨上一个边界 则左边界不变
// 如 字符串 "abba"
left = cur > left? cur :left;
}
map.put(s.charAt(i),i);
}
return Math.max(max, len-left);
}
}
复杂度分析
- 时间复杂度：$O(n)$ 如字符串长度为 $n$ 则所有元素执行一遍
- 空间复杂度：$O(n)$ 如所有的字符串都不重复，则
map需要保存 $n$ 个元素
方法二 滑动窗口
解题思路
- 我们只要把队列的左边的元素移出就行了，直到满足题目要求！(不在出现重复字符串)
- 一直维持这样的队列，找出队列出现最长的长度时候，求出解！
- 时间复杂度：$O(n)$
代码
python
class Solution(object):
def lengthOfLongestSubstring(self, s):
if not s: return 0
left = 0
curLen = 0 # 当前长度
maxLen = 0 # 最长字符串
lookup = set() # 用来存储滑动的字符串
for i in range(len(s)):
curLen +=1
# 这里是while循环，当重复字符串一直在集合当中，会一直删除左边的字符串，直到删除重复字符串
while s[i] in lookup:
lookup.remove(s[left])
left += 1
curLen -= 1
#比较当前长度和最长长度
if curLen > maxLen:maxLen=curLen
lookup.add(s[i])
return maxLen
java
class Solution {
public int lengthOfLongestSubstring(String s) {
int left = 0;
Set<Character> lookup = new HashSet<>();
int cul_len = 0;
int max_len = 0;
for (int i=0;i<s.length();i++) {
cul_len += 1;
while (lookup.contains(s.charAt(i))) {
lookup.remove(s.charAt(left));
left += 1;
cul_len -= 1;
}
if(cul_len>max_len)
max_len = cul_len;
lookup.add(s.charAt(i));
}
return max_len;
}
}
- 如果你觉得本文对你有帮助，请点赞👍支持
- 如果有疑惑或者表达不到位的额地方 ，请在下面👇评论区指出