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

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) 时间内找到最长无重复字符子串。