3.无重复字符的最长子串(Medium)
# 题目描述
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
# 样例
Input: "abcabcbb"
Output: 3
# 解释 因为无重复字符的最长子串是 "abc",所以其长度为 3。
1
2
3
2
3
# 题解
建立一个256位大小的整型数组freg,用来建立字符和其出现位置之间的映射。维护一个滑动窗口,窗口内的都是没有重复的字符,去尽可能的扩大窗口的大小,窗口不停的向右滑动。
(1)如果当前遍历到的字符从未出现过,那么直接扩大右边界; (2)如果当前遍历到的字符出现过,则缩小窗口(左边索引向右移动),然后继续观察当前遍历到的字符; (3)重复(1)(2),直到左边索引无法再移动; (4)维护一个结果res,每次用出现过的窗口大小来更新结果res,最后返回res获取结果。
# Python示例
使用 辅助数组
作为访问记录
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
visited = {} # 辅助数组
for char in s:
visited[char] = 0
l, r = 0, -1
maxSubString = 0
while l < len(s):
if r + 1 < len(s) and not visited[s[r + 1]]:
r += 1
visited[s[r]] = 1
maxSubString = max(maxSubString, r - l + 1) # 只有右扩的话才有意义
else:
visited[s[l]] -= 1
l += 1
return maxSubString
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
使用 集合
作为访问记录
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
l, r = 0, -1
ans = 0
visited = set() # 集合
while l < len(s):
if r + 1 < len(s) and s[r + 1] not in visited:
r += 1
visited.add(s[r])
else:
visited.remove(s[l])
l += 1
ans = max(ans, r - l + 1)
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
编辑 (opens new window)
上次更新: 2022/10/25, 02:40:54