当前位置：首页>python>Python题库第4题:找出不含有重复字符的最长子串的长度

Python题库第4题:找出不含有重复字符的最长子串的长度

2026-10-11 08:22:12

Python，速成心法

敲代码，查资料，问Ai

练习，探索，总结，优化

★★★★★博文创作不易，源码代码的过程中，如有疑问的地方，欢迎大家指正留言交流。喜欢的老铁可以多多点赞+收藏分享+置顶，小红牛在此表示感谢。★★★★★

Python打包教程07：还不会用--add-data参数，添加资源文件吗？

Python打包教程04：UPX安装与使用（减小.exe体积）

Python打包教程03：PyInstaller命令使用指南

Python教程：PyCharm安装过程中遇到的中英文对照表

和Python编程相关的，中英文对照词汇表

2025年Python和pycharm安装下载教程

Python零基础教程：小白入门自学知识点大纲

Python教程：找到字符串中最长回文子串（上海自来水来自海上）

Python题库第2题：找出三数之和为零的数据

Python题库第3题：3[a2[c]]字符串解码

1.无重复字符的最长子串（中等难度）题目描述：给定一个字符串 s，请你找出其中不含有重复字符的，最长子串的长度。

注意：子串必须是连续的，子序列不是子串。

# 示例输入: s = "abcabcbb"输出: 3解释: 无重复字符的最长子串是 "abc"，长度为 3。输入: s = "bbbbb"输出: 1解释: 最长子串是 "b"，长度为 1。输入: s = "pwwkew"输出: 3解释: 最长子串是 "wke" 或 "kew"，长度为 3。输入: s = ""输出: 0

2.要求：时间复杂度 O(n)，n 为字符串长度。空间复杂度 O(min(n, |字符集大小|))，通常认为 O(1) 或 O(字符集)。不能使用 set 以外的第三方库，但 set 和 dict 允许。

3.思路说明

滑动窗口：维护一个窗口 [left, right]，保证窗口内的所有字符都不重复。

哈希表记录：使用字典 char_index_map 存储每个字符最近一次出现的位置。

移动左边界：当遇到重复字符时，左边界直接跳到该字符上次出现位置的下一个位置（但必须确保左边界不会向左移动，所以还需要与当前 left 取最大值）。

更新最大长度：每次迭代后计算当前窗口长度并更新全局最大值。

时间复杂度 O(n)：每个字符最多被左右指针各访问一次。

空间复杂度 O(min(n, |字符集|))：最坏情况存储 n 个不同字符，但字符集大小有限（如 ASCII 128），可视为 O(1)。

此解法是解决“无重复字符的最长子串”的标准滑动窗口方法，满足要求。

↓ 完整源码如下 ↓

# -*- coding: utf-8 -*-# @Author : 小红牛# 微信公众号：wdPythondef length_of_longest_substring(s: str) -> int:    """    返回无重复字符的最长子串长度。    参数:        s: 输入字符串    返回:        int: 最长无重复子串的长度    """    # 用于记录字符最近一次出现的位置（索引）    char_index_map = {}    left = 0          # 窗口左边界    max_len = 0    for right, ch in enumerate(s):        # 如果字符已经在窗口内出现，移动左边界到上次出现位置的下一位        if ch in char_index_map and char_index_map[ch] >= left:            left = char_index_map[ch] + 1        # 更新字符最新位置        char_index_map[ch] = right        # 更新最大长度        current_len = right - left + 1        if current_len > max_len:            max_len = current_len    return max_len# 测试用例if __name__ == "__main__":    print(length_of_longest_substring("abcabcbb"))  # 3    print(length_of_longest_substring("bbbbb"))     # 1    print(length_of_longest_substring("pwwkew"))    # 3    print(length_of_longest_substring(""))          # 0    print(length_of_longest_substring("aab"))       # 2    print(length_of_longest_substring("dvdf"))      # 3