• 【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

  • 相关阅读:
    一次跨域问题的记录
    React:构建Web应用的未来
    封装axios并实现发送请求前如果有正在执行的请求就取消请求
    如何成功地将 OKR 推广到您的组织
    React框架的基本运行原理与组件定义方式
    32单片机基础:OLED调试工具的使用
    大数定律与中心极限定理
    Elasticsearch高级之-集群搭建,数据分片
    Java调试谷歌PC浏览器,控制操作网页
    Redis官方开源的可视化管理工具 - RedisInsight
  • 原文地址:https://blog.csdn.net/CSDNLHCC/article/details/133800522