LeetCode热题1003.无重复字符的最长子串

LeetCode 热题100 | 3. 无重复字符的最长子串

大家好，今天我们来解决一道经典的算法题——无重复字符的最长子串。这道题在 LeetCode 上被标记为中等难度，要求我们找出一个字符串中不含有重复字符的最长子串的长度。下面我将详细讲解解题思路，并附上 Python 代码实现。

---

题目描述

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

示例：

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

---

解题思路

这道题的核心是找到一个不包含重复字符的子串，并返回其最大长度。我们可以使用 滑动窗口 来解决这个问题。

核心思想

滑动窗口：

使用两个指针 left 和 right 表示当前子串的左右边界。使用一个哈希集合 char_set 来记录当前子串中的字符。

窗口扩展：

移动 right 指针，将字符加入 char_set。如果字符已经存在于 char_set 中，则移动 left 指针，直到 char_set 中不再有重复字符。

更新最大长度：

每次扩展窗口后，更新最大子串长度。

---

代码实现 def lengthOfLongestSubstring(s): """ :type s: str :rtype: int """ char_set = set() # 用于记录当前子串中的字符 left = 0 # 滑动窗口的左边界 max_length = 0 # 最大子串长度 for right in range(len(s)): # 如果当前字符已经存在于集合中，移动左指针 while s[right] in char_set: char_set.remove(s[left]) left += 1 # 将当前字符加入集合 char_set.add(s[right]) # 更新最大长度 max_length = max(max_length, right - left + 1) return max_length

---

代码解析

初始化：

char_set 用于记录当前子串中的字符。left 是滑动窗口的左边界，初始为 0。max_length 是最大子串长度，初始为 0。

滑动窗口扩展：

遍历字符串，移动 right 指针。如果当前字符 s[right] 已经存在于 char_set 中，则移动 left 指针，并从 char_set 中移除 s[left]，直到 char_set 中不再有重复字符。

更新最大长度：

将当前字符 s[right] 加入 char_set。更新 max_length 为当前窗口长度 right - left + 1 和 max_length 的较大值。

返回结果：

返回 max_length。

---

复杂度分析 时间复杂度：O(n)，其中 n 是字符串的长度。每个字符最多被访问两次（left 和 right 各一次）。空间复杂度：O(min(m, n))，其中 m 是字符集的大小（ASCII 字符集为 128），n 是字符串的长度。char_set 的大小最多为字符集的大小。

---

示例运行 示例 1 # 输入: s = "abcabcbb" s = "abcabcbb" print(lengthOfLongestSubstring(s)) # 输出: 3

解释：

最长无重复字符的子串是 "abc"，长度为 3。 示例 2 # 输入: s = "bbbbb" s = "bbbbb" print(lengthOfLongestSubstring(s)) # 输出: 1

解释：

最长无重复字符的子串是 "b"，长度为 1。 示例 3 # 输入: s = "pwwkew" s = "pwwkew" print(lengthOfLongestSubstring(s)) # 输出: 3

解释：

最长无重复字符的子串是 "wke"，长度为 3。

---

总结

通过滑动窗口法，我们可以高效地找到无重复字符的最长子串。这种方法的时间复杂度为 O(n)，空间复杂度为 O(min(m, n))，能够处理较大的输入规模。希望这篇题解对你有帮助！如果还有其他问题，欢迎继续提问！

关注我，获取更多算法题解和编程技巧！