给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
xxxxxxxxxx
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
xxxxxxxxxx
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
xxxxxxxxxx
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
最直接的方式是滑动窗口,它的想法非常朴素:如果从索引 到 之间的子字符串 已经被检查为没有重复字符。我们只需要检查 对应的字符是否已经存在于子字符串 中。
通过使用 HashSet 作为滑动窗口,我们可以用 的时间来完成对字符是否在当前的子字符串中的检查。
滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合,即 。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如,我们将 向右滑动 个元素,则它将变为 。
我们使用 HashSet 将字符存储在当前窗口 (最初 )中。 然后我们向右侧滑动索引 ,如果它不在 HashSet 中,我们会继续滑动 。直到 已经存在于 HashSet 中。此时,我们找到的没有重复字符的最长子字符串将会以索引 开头。如果我们对所有的 这样做,就可以得到答案。
xxxxxxxxxx
def lengthOfLongestSubstring(self, s: str) -> int:
i = 0
j = 0
max_length = 0
check = set()
while (i < len(s) and j < len(s)):
if s[j] not in check:
check.add(s[j])
j += 1
max_length = max(max_length, j - i)
else:
check = set()
i += 1
j = i
return max_length
事实上,上述方法还可以进一步优化,如果出现重复元素( 已经存在于 HashSet 中)就直接将 移动至 中 元素对应的位置之后,这样就可以不需要对每一个 都进行上述操作了。
我的解答:
xxxxxxxxxx
def lengthOfLongestSubstring(self, s: str) -> int:
check = set()
max_length = 0
i = 0
j = 0
while (j < len(s)):
if s[j] not in check:
check.add(s[j])
j += 1
max_length = max(j - i, max_length)
else: # 将 i 移动到重复元素之后
check.remove(s[i])
i += 1
return max_length