问题描述

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

示例：

• 输入：s = "abcabcbb"
• 输出：3
• 解释：无重复字符的最长子串是 "abc"，其长度为 3。

解题思路：滑动窗口 + 哈希表

核心思想

使用滑动窗口（双指针）和哈希表来解决该问题，时间复杂度为 O(n)，空间复杂度为 O(min(m, n))（m 为字符集大小）。

1. 双指针定义

   • left：窗口左边界，用于收缩窗口。
   • right：窗口右边界，用于扩展窗口。
   • 窗口 [left, right] 内始终保持无重复字符。

2. 哈希表作用

   • 记录每个字符最后一次出现的位置。
   • 快速判断当前字符是否在窗口内重复。

3. 窗口维护规则

   • 当前字符未出现过：扩展窗口（right 右移）。
   • 当前字符已出现过：收缩窗口（left 移动到该字符上一次出现位置的下一位）。
   • 每一步计算当前窗口长度，更新最大长度。

代码实现（Python）

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_index = {}  # 记录字符最近出现的位置
        left = 0
        max_len = 0

        # 右指针遍历字符串
        for right in range(len(s)):
            char = s[right]

            # 如果字符已出现过
            if char in char_index:
                # 更新当前字符的最新位置，防止 left 回退
                left = max(left, char_index[char] + 1)

            char_index[char] = right

            # 计算当前窗口长度，更新最大值
            max_len = max(max_len, right - left + 1)

        return max_len

关键知识点讲解

1. 滑动窗口（Sliding Window）

滑动窗口是一种线性时间的双指针技巧，常用于处理子数组或子串问题：

• 本质：用两个指针动态维护一个区间，避免暴力枚举所有子串。
• 优势：将 O(n²) 暴力解法优化到 O(n)。
• 适用场景：最长/最短子串、子数组和、连续子数组等问题。

2. 哈希表优化

使用字典 char_index 存储 {字符: 最后出现位置}，查询时间为 O(1)。

• 对比 HashSet 版本：
  • HashSet 版：发现重复时需要逐个移动 left 并删除字符，效率稍低。
  • 哈希表版：直接定位到重复字符的上一次位置，一步到位更新 left，更高效。

3. 边界处理细节

• left = char_index[char] + 1：必须加 1，保证窗口内不再包含重复字符。
• 只有当重复字符的位置 >= left 时才更新 left，避免窗口左边界回退（如字符在窗口外重复）。
• 窗口长度计算：right - left + 1（因为区间是闭区间）。

复杂度分析

• 时间复杂度：O(n)，right 指针遍历字符串一次，left 指针最多随 right 移动 n 次，总体线性时间。
• 空间复杂度：O(min(m, n))，最多存储所有不重复字符，m 为字符集大小（如 ASCII 码为 128）。