题目
输入一个字符串,返回该串中最长不含重复字符的子串长度
例子
'abcabcbb' -> 3
'bbbbbb' -> 1
假设
输入的字符串一定不为None或空串
输入的字符串中的字符仅为小写英文字母
tips
网站解法
解法2:
def lengthOfLongestSubstring(s):
# 哈希集合，记录每个字符是否出现过
occ = set()
n = len(s)
# 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
rk, ans = -1, 0
for i in range(n):
if i != 0:
# 左指针向右移动一格，移除一个字符
occ.remove(s[i - 1])
while rk + 1 < n and s[rk + 1] not in occ:
# 不断地移动右指针
occ.add(s[rk + 1])
rk += 1
# 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = max(ans, rk - i + 1)
return ans
性能
时间复杂度O(n)
空间复杂度O(n)
双指针思路
def lengthOfLongestSubstring(s):
occ = set()
n = len(s)
rk, ans = 0, 0
for i in range(n):
# 每次循环把当前的元素删除，然后再去检查是否有最大子串
if i != 0:
occ.remove(s[i-1])
# occ 中是i到rk的最大子串 ， 当rk指向元素在set中，那么就停止循环了，让occ不断remove，直到当前rk可以入set
while rk < n and s[rk] not in occ:
occ.add(s[rk])
rk += 1
ans = max(ans, rk -i)
return rk
