企业官网建设流程全解析

LeetCode 3：无重复字符的最长子串 | 滑动窗口

引言

无重复字符的最长子串（Longest Substring Without Repeating Characters）是 LeetCode 第 3 题，难度为 Medium。题目要求在字符串中找到不含重复字符的最长子串的长度。

这道题使用滑动窗口算法，在 O(n) 时间内解决。滑动窗口维护一个不含重复字符的窗口，通过移动左右指针来扩展或收缩窗口。

问题分析

题目描述

给定字符串 s，找到不含重复字符的最长子串的长度。

关键点

• 使用哈希表记录每个字符最后一次出现的位置
• 右指针扩展窗口，左指针收缩窗口
• 当遇到重复字符时，左指针跳到重复字符上一次出现位置的后面

算法实现

Python 实现

def lengthOfLongestSubstring(s): char_index = {} left = 0 max_len = 0 for right, char in enumerate(s): if char in char_index and char_index[char] >= left: left = char_index[char] + 1 char_index[char] = right max_len = max(max_len, right - left + 1) return max_len

算法详解

• char_index：记录每个字符最近一次出现的索引
• left：窗口左边界
• right：窗口右边界，遍历字符串时扩展

当遇到已存在的字符且其在窗口内（char_index[char] >= left），收缩左边界到重复字符上一次出现位置的后面。

复杂度分析

时间复杂度

O(n)，每个字符最多被访问两次（左右指针各一次）。

空间复杂度

O(min(n, m))，其中 m 是字符集大小。

总结

滑动窗口是解决子串问题的有效方法。通过维护一个窗口和哈希表，可以在 O(n) 时间内找到最长无重复字符子串。