【LeetCode】3. 无重复字符的最长子串

1 问题

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

2 答案

我的不对

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

输入

s =
"dvdf"
1
2

输出

2
1

预期结果

3
1

正确答案

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3 知识点

3.1哈希表

类似于python中的字典。也叫做散列表。是根据关键码值（Key Value）直接进行访问的数据结构。
哈希表通过「键 key 」和「映射函数 Hash(key) 」计算出对应的「值 value」，把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做「哈希函数（散列函数）」，存放记录的数组叫做「哈希表（散列表）」。

https://blog.csdn.net/zy_dreamer/article/details/131036258

3.2滑动窗口

是双指针算法的一种，基本思路为维护一个窗口，然后从前往后遍历元素进行运算。

https://blog.csdn.net/qq_54850598/article/details/127863026