给定一个字符串 s
,请你找出其中不含有重复字符的 最长子串
的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
请注意,你的答案必须是 子串 的长度,“pwke” 是一个子序列,不是子串。
我的不对
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
list = []
l = 0
for i in range(len(s)):
if s[i] in list:
list = []
list.append(s[i])
else:
list.append(s[i])
if len(list) > l:
l = len(list)
return l
输入
s =
"dvdf"
输出
2
预期结果
3
正确答案
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
max_len, hashmap = 0, {} # hashmap 用于存放字符,去重
start = 0
for end in range(len(s)):
hashmap[s[end]] = hashmap.get(s[end], 0) + 1
if len(hashmap) == end - start + 1: # 考察第0个元素时,窗口大小实际是 end - start + 1
max_len = max(max_len, end - start + 1) # 更新最大值
while end - start + 1 > len(hashmap): # 遍历删除前面的重复值
head = s[start]
hashmap[head] -= 1
if hashmap[head] == 0:
del hashmap[head]
start += 1
return max_len
类似于python中的字典。也叫做散列表。是根据关键码值(Key Value)直接进行访问的数据结构。
哈希表通过「键 key 」和「映射函数 Hash(key) 」计算出对应的「值 value」,把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做「哈希函数(散列函数)」,存放记录的数组叫做「哈希表(散列表)」。
https://blog.csdn.net/zy_dreamer/article/details/131036258
是双指针算法的一种,基本思路为维护一个窗口,然后从前往后遍历元素进行运算。
https://blog.csdn.net/qq_54850598/article/details/127863026