无重复字符的最长子串

🕗 发布于 2024-04-13 12:31 python

给定一个半角英文字符串，找出无重复字符的最长子串长度。

(笔记模板由python脚本于2024年04月11日 23:19:44创建，本篇笔记适合初通Python，熟悉六大基本数据_{(str字符串、int整型、float浮点型、list列表、tuple元组、set集合、dict字典)}的coder翻阅)

【学习的细节是欢悦的历程】

Python 官网：https://www.python.org/
Free：大咖免费“圣经”教程《 python 完全自学教程》，不仅仅是基础那么简单……
地址：https://lqpybook.readthedocs.io/

自学并不是什么神秘的东西，一个人一辈子自学的时间总是比在学校学习的时间长，没有老师的时候总是比有老师的时候多。
—— 华罗庚

My CSDN主页、My HOT博、My Python 学习个人备忘录
好文力荐、老齐教室

给定一个半角英文字符串 无重复字符最长子串 (找出无重复字符的最长子串长度)

本文质量分：

【 $96$ 】
本文地址： https://blog.csdn.net/m0_57158496/article/details/137657295

CSDN质量分查询入口：http://www.csdn.net/qc

目录

◆ 无重复字符的最长子串
- 1、题目描述
- 2、算法解析
- - 2.1 `for`循环嵌套遍历
  - 2.2 我的算法优化
  - 2.3 力扣题解大神算法
- 3、代码效率测试
- - 3.1 代码力扣提交信息
  - 3.2 本地代码运行用时测试
- 4、完整源码(Python)

◆ 无重复字符的最长子串

1、题目描述

力扣题库第3题

【原题地址：https://leetcode.cn/problems/longest-substring-without-repeating-characters/】

回页目录

2、算法解析

我最能想到的本题目解决方案是用“循环嵌套”，我用的for嵌套。代码写完发现，循环次数太多，用时太久。试着优化成单层循环，剔除了大量不必要的遍历，缩短了一半的时间。后来习读大神的“双指针”代码，力扣提交，样例用时比我“优化”代码用时<font size=> $1 / 3$ 还少！

2.1 `for`循环嵌套遍历

代码解析

一般常规解法：双层for嵌套遍历字符串。外层控制字符串起点，内层搜索非重复字符串并记录最大长度。此法缺点：循环次数太多。

Python代码


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        if n < 2: return n
        
        l = 0 # 非重复字母长度初值。
        ss = '' # 搜索到的非重复字符串初值。

        for i in range(n):
            for j in range(i, n):
                if s[j] not in ss: ss += s[j]
                else:
                    if len(ss) > l: l = len(ss)
                    ss = '' # 非重复字符串变量清零，方便存储下一个非重复字符串。
                    break
                
        return l

回页目录

2.2 我的算法优化

代码解析

仔细审验上段代码，用if控制内存循环遍历到有字符重复时，记录无重复字符串子串长度后结束循环，剔除不必要的循环遍历。

Python代码


class Solution2:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        if n < 2: return n
        a = l = 0

        for i in range(n):
            ss = s[a:i]
            local = s[i]
            n = len(ss) 
            if local in ss:
                l = n if n > l else l

                while 1:

                    if s[i-1] == local:
                        a = i
                        break 
                        
                    i -= 1
        
        n = len(s[a:])        
        return n if n > l else l

回页目录

2.3 力扣题解大神算法

大神代码I

Python代码


class Solution3: # 力扣题解大神代码I
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0
        left = 0
        lookup = set()
        n = len(s)
        max_len = 0
        cur_len = 0
        for i in range(n):
            cur_len += 1
            while s[i] in lookup:
                lookup.remove(s[left])
                left += 1
                cur_len -= 1
            if cur_len > max_len:max_len = cur_len
            lookup.add(s[i])
        return max_len

大神代码II

Python代码


class Solution4: # 力扣题解大神代码II
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic, res, i = {}, 0, -1
        for j in range(len(s)):
            if s[j] in dic:
                i = max(dic[s[j]], i) # 更新左指针 i
            dic[s[j]] = j # 哈希表记录
            res = max(res, j - i) # 更新结果
        return res

回页目录

3、代码效率测试

3.1 代码力扣提交信息

代码力扣提交截屏图片

一般循环遍历代码

优化算法单层循环代码

$大神代码$

$I$ .

$I I$ .

回页目录

3.2 本地代码运行用时测试

代码运行效果截屏图片

代码调用


if __name__ == '__main__':
    s = 'ACaA5abababc 5dabcj5gh'
    n = 100000
    print(f"\n试码用例字符串：\n{s = }\n\n运行代码{n}次用时：")

    s1 = Solution()
    t = time()
    for i in range(n):
       s1.lengthOfLongestSubstring(s)
    
    print(f"\n常规写法：\n{s1.lengthOfLongestSubstring(s) = }")
    print(f"{time()-t:.2f}s")
    
    
    s2 = Solution2()
    t = time()
    for i in range(10000):
       s2.lengthOfLongestSubstring(s)
    
    print(f"\n优化算法：\n{s2.lengthOfLongestSubstring(s) = }")
    print(f"{time()-t:.2f}s")

    s3 = Solution3()
    t = time()
    for i in range(10000):
       s3.lengthOfLongestSubstring(s)
    
    print(f"\n力扣题库大佬题解代码：\n{s3.lengthOfLongestSubstring(s) = }")
    print(f"{time()-t:.2f}s")

回页目录

4、完整源码(Python)

(源码较长，点此跳过源码)

#!/sur/bin/nve python
# coding: utf-8
from time import time


class Solution4: # 力扣大神代码II
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic, res, i = {}, 0, -1
        for j in range(len(s)):
            if s[j] in dic:
                i = max(dic[s[j]], i) # 更新左指针 i
            dic[s[j]] = j # 哈希表记录
            res = max(res, j - i) # 更新结果
        return res



# 一般常规解法：双层for嵌套遍历字符串。外层控制字符串起点，内层搜索非重复字符串并记录最大长度。此法缺点：循环次数太多。
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        if n < 2: return n
        
        l = 0 # 非重复字母长度初值。
        ss = '' # 搜索到的非重复字符串初值。

        for i in range(n):
            for j in range(i, n):
                if s[j] not in ss: ss += s[j]
                else:
                    if len(ss) > l: l = len(ss)
                    ss = '' # 非重复字符串变量清零，方便存储下一个非重复字符串。
                    break
                
        return l


class Solution2:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        if n < 2: return n
        a = l = 0

        for i in range(n):
            ss = s[a:i]
            local = s[i]
            n = len(ss) 
            if local in ss:
                l = n if n > l else l

                while 1:

                    if s[i-1] == local:
                        a = i
                        break 
                        
                    i -= 1
        
        n = len(s[a:])        
        return n if n > l else l


class Solution3: # 力扣大神代码I
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0
        left = 0
        lookup = set()
        n = len(s)
        max_len = 0
        cur_len = 0
        for i in range(n):
            cur_len += 1
            while s[i] in lookup:
                lookup.remove(s[left])
                left += 1
                cur_len -= 1
            if cur_len > max_len:max_len = cur_len
            lookup.add(s[i])
        return max_len


if __name__ == '__main__':
    s = 'ACaA5abababc 5dabcj5gh'
    n = 100000
    print(f"\n试码用例字符串：\n{s = }\n\n运行代码{n}次用时：")

    s1 = Solution()
    t = time()
    for i in range(n):
       s1.lengthOfLongestSubstring(s)
    
    print(f"\n常规写法：\n{s1.lengthOfLongestSubstring(s) = }")
    print(f"{time()-t:.2f}s")
    
    
    s2 = Solution2()
    t = time()
    for i in range(10000):
       s2.lengthOfLongestSubstring(s)
    
    print(f"\n优化算法：\n{s2.lengthOfLongestSubstring(s) = }")
    print(f"{time()-t:.2f}s")

    s3 = Solution3()
    t = time()
    for i in range(10000):
       s3.lengthOfLongestSubstring(s)
    
    print(f"\n力扣题库大神题解代码I：\n{s3.lengthOfLongestSubstring(s) = }")
    print(f"{time()-t:.2f}s")

    s4 = Solution4()
    t = time()
    for i in range(10000):
       s4.lengthOfLongestSubstring(s)
    
    print(f"\n力扣题库大神题解代码II：\n{s4.lengthOfLongestSubstring(s) = }")
    print(f"{time()-t:.2f}s")

回页首

上一篇：插值字符串格式代码中的“!”(Python)_{(读到插值字符串格式化代码中有“!”，进行了一番探究，了解了其中的一点“隐秘”，在此共享)}
下一篇：

我的HOT博：

本次共计收集 311 篇博文笔记信息，总阅读量43.82w。数据于2024年03月22日 00:50:22完成采集，用时6分2.71秒。阅读量不小于6.00k的有 $7$ 篇。

001
标题：让QQ群昵称色变的神奇代码
_{(浏览阅读 5.9w )}
地址：https://blog.csdn.net/m0_57158496/article/details/122566500
点赞：25 收藏：86 评论：17
摘要：让QQ昵称色变的神奇代码。
首发：2022-01-18 19:15:08
最后编辑：2022-01-20 07:56:47
002
标题：Python列表(list)反序(降序)的7种实现方式
_{(浏览阅读 1.1w )}
地址：https://blog.csdn.net/m0_57158496/article/details/128271700
点赞：8 收藏：35 评论：8
摘要：Python列表(list)反序(降序)的实现方式：原址反序，list.reverse()、list.sort()；遍历，全数组遍历、1/2数组遍历；新生成列表，resersed()、sorted()、负步长切片[::-1]。
首发：2022-12-11 23:54:15
最后编辑：2023-03-20 18:13:55
003
标题：pandas 数据类型之 DataFrame
_{(浏览阅读 9.7k )}
地址：https://blog.csdn.net/m0_57158496/article/details/124525814
点赞：7 收藏：36
摘要：pandas 数据类型之 DataFrame_panda dataframe。
首发：2022-05-01 13:20:17
最后编辑：2022-05-08 08:46:13
004
标题：个人信息提取(字符串)
_{(浏览阅读 8.2k )}
地址：https://blog.csdn.net/m0_57158496/article/details/124244618
点赞：2 收藏：15
摘要：个人信息提取(字符串)_个人信息提取python。
首发：2022-04-18 11:07:12
最后编辑：2022-04-20 13:17:54
005
标题：Python字符串居中显示
_{(浏览阅读 7.6k )}
地址：https://blog.csdn.net/m0_57158496/article/details/122163023
评论：1
006
标题：罗马数字转换器|罗马数字生成器
_{(浏览阅读 7.5k )}
地址：https://blog.csdn.net/m0_57158496/article/details/122592047
摘要：罗马数字转换器|生成器。
首发：2022-01-19 23:26:42
最后编辑：2022-01-21 18:37:46
007
标题：回车符、换行符和回车换行符
_{(浏览阅读 6.0k )}
地址：https://blog.csdn.net/m0_57158496/article/details/123109488
点赞：2 收藏：3
摘要：回车符、换行符和回车换行符_命令行回车符。
首发：2022-02-24 13:10:02
最后编辑：2022-02-25 20:07:40

推荐条件阅读量突破6.00k (更多热博，请点击蓝色文字跳转翻阅)

截屏图片

(此文涉及ChatPT，曾被csdn多次下架，前几日又因新发笔记被误杀而落马。躺“未过审”还不如回收站，回收站还不如永久不见。😪值此年底清扫，果断移除。留此截图，以识“曾经”。2023-12-31)

回页首

精品文章：

好文力荐：齐伟书稿《python 完全自学教程》 Free连载(已完稿并集结成书，还有PDF版本百度网盘永久分享，点击跳转免费🆓下载。)
OPP三大特性：封装中的property
通过内置对象理解python'
正则表达式
python中“*”的作用
Python 完全自学手册
海象运算符
Python中的 `!=`与`is not`不同
学习编程的正确方法

来源：老齐教室

◆ Python 入门指南【Python 3.6.3】

好文力荐：

全栈领域优质创作者——[寒佬]_{(还是国内某高校学生)}博文“非技术文—关于英语和如何正确的提问”，“英语”和“会提问”是编程学习的两大利器。
【8大编程语言的适用领域】先别着急选语言学编程，先看它们能干嘛
靠谱程序员的好习惯
大佬帅地的优质好文“函数功能、结束条件、函数等价式”三大要素让您认清递归

CSDN实用技巧博文：

原文地址：https://blog.csdn.net/m0_57158496/article/details/137657295

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Linux命令-dpkg命令（Debian Linux系统上安装、创建和管理软件包）
下一篇：【机器学习300问】64、简写出常见的激活函数及其导数？

MySQL数据库基础
在过去的mysql中主要是使用的utf8mb3，但是mysql显示的就是utf8，中mysql8中区分显示了。类似于不同的编译器，虽然C/C++的代码是一样的，但是预处理、编译、汇编、链接这些过程却不
阅读更多2024-09-30
Percona Monitoring and Management
Percona Monitoring and Management (PMM)是一款开源的专用于管理和监控MySQL、MongoDB、PostgreSQL。
阅读更多2024-09-30
鸿蒙开发（NEXT/API 12）【已连接穿戴设备查询】手机侧应用开发
Wear Engine提供查询用户已连接的穿戴设备列表（即支持Wear Engine能力且与手机侧运动健康App处于连接状态的穿戴设备）的接口。
阅读更多2024-09-30
Redis数据库
本篇文章介绍了redis的相关知识，并使用springboot集成redis，实现缓存和分布式锁，后续会对文章勘误及更新~~
阅读更多2024-09-30
旧版的存档
【代码】旧版的存档。
阅读更多2024-09-30
Spring Boot 封装统一返回结果及全局异常处理
为了更细致地控制异常处理，我们可以定义一些自定义异常。然后，在全局异常处理器中添加对自定义异常的处理。通过封装统一的返回结果和全局异常处理，我们可以让Spring Boot应用更加健壮和易于维护。这种
阅读更多2024-09-30
【C++】IO流
C++IO流，包含输入输出流、文件流、字符流
阅读更多2024-09-30
低至1元/小时：国庆七天，30元通关《黑神话：悟空》！
随着《黑神话：悟空》自8月20日全球同步上线，正式登陆PC、PS5平台以来，以其精湛的画面和流畅的战斗体验，在发售三天后，该作的全平台销量超过1000万套，打破中国游戏历史记录，被媒体称为“中国首款3
阅读更多2024-09-30
阿里巴巴国际站获取商品详情item_get接口技术分享
item_get API接口是阿里巴巴开放平台提供的一个重要接口，它允许商家通过API调用，获取阿里巴巴平台上的商品详细信息。这些信息包括商品标题、价格、库存、属性、描述等，为商家提供了全面、准确的商
阅读更多2024-09-30
软件测试谣言二三事，认真你就输了
软件测试的职业寿命，取决于互联网行业能存活多久，至少目前看来，这个职业没有消失的风险，至于你能在这个职业待多久，那取决于你自己的能力，我见过不少超过35岁的老员工还在测试的职位上兢兢业业。以广州为例，
阅读更多2024-09-30

无重复字符的最长子串

◆ 无重复字符的最长子串

1、题目描述

2、算法解析

2.1 for循环嵌套遍历

2.2 我的算法优化

2.3 力扣题解大神算法

3、代码效率测试

3.1 代码力扣提交信息

3.2 本地代码运行用时测试

4、完整源码(Python)

相关文章

2.1 `for`循环嵌套遍历