最长不重复子串（Longest Substring Without Repeating Characters）

字数 2532 2025-12-14 08:14:05

最长不重复子串（Longest Substring Without Repeating Characters）

最长不重复子串是一个经典的字符串算法问题，其描述为：给定一个字符串，找出其中不含有重复字符的最长子串的长度。

1. 问题描述

假设输入字符串为 "abcabcbb"，我们需要找到其中最长的连续子串，使得这个子串中的字符互不重复。对于这个例子，答案应该是 3，因为最长的不重复子串是 "abc"。

输入: 一个字符串 s (例如 "abcabcbb")
输出: 一个整数，表示最长不重复子串的长度

2. 从直观思路出发

我们先从一个最朴素的想法开始。要找到一个不重复的子串，最容易想到的方法是枚举所有可能的子串，然后检查其中是否有重复字符。

具体步骤：

用两个指针（或索引）i 和 j 表示子串的起始和结束位置。
对于每个起始位置 i，将 j 从 i 开始往后移动，每次加入一个新字符，并检查新字符是否在子串中出现过。如果没有重复，就更新最大长度；如果重复了，就停止移动 j，然后移动 i 到下一位。
这种方法的时间复杂度约为 O(n³)，因为检查是否有重复字符需要 O(n) 时间，加上两层循环枚举，效率很低。我们需要优化。

3. 使用滑动窗口优化

我们可以用“滑动窗口”的思想来避免不必要的检查。滑动窗口是表示当前不重复子串的一个区间 [left, right]。我们通过一个集合来记录窗口中已有的字符，这样就能在 O(1) 时间内判断新字符是否在窗口中。

具体步骤：

初始化一个空集合 char_set 用来存放窗口中的字符。
初始化两个指针：left = 0 和 right = 0，表示窗口的左右边界（左闭右开）。
初始化一个变量 max_len = 0 记录答案。
遍历字符串，每次将 s[right] 加入窗口：
- 如果 s[right] 不在 char_set 中，说明可以扩展窗口，将其加入集合，然后更新 max_len = max(max_len, right - left + 1)，接着将 right 右移。
- 如果 s[right] 已经在 char_set 中，说明出现了重复，这时我们需要移动 left 指针，直到窗口中不包含这个重复字符为止。每次移动 left 时，从集合中移除 s[left]，然后 left++。
重复上述过程直到 right 到达字符串末尾。

示例：s = "abcabcbb"

窗口变化过程：
- [a] -> 长度 1
- [a,b] -> 长度 2
- [a,b,c] -> 长度 3
- 加入 a 时重复，移动 left 直到移除之前的 a，窗口变为 [b,c,a] -> 长度 3
- 加入 b 重复，移动 left 移除 b，窗口变为 [c,a,b] -> 长度 3
- 加入 c 重复，移动 left 移除 c，窗口变为 [a,b,c] -> 长度 3
- 加入 b 重复，移动 left 直到移除 b，窗口变为 [c,b] -> 长度 2
- 加入 b 重复，移动 left 移除 b，窗口变为 [b] -> 长度 1
最长长度始终为 3。

这种方法将时间复杂度降为 O(n)，因为每个字符最多被加入和移除集合一次。

4. 进一步优化：使用哈希表记录位置

上面用集合的方法，在出现重复时需要不断移动 left 直到移除重复字符。这一步可以优化，如果我们用一个哈希表记录每个字符最近出现的位置，那么当遇到重复字符时，我们可以直接让 left 跳转到重复字符上次出现位置的下一位，而不是一步步移动。

具体步骤：

初始化一个哈希表 char_index，键是字符，值是该字符最近一次出现的索引。
初始化 left = 0，max_len = 0。
遍历字符串，对于每个索引 right：
- 如果当前字符 s[right] 在哈希表中，并且其上次出现位置 index 大于等于 left，说明重复出现在当前窗口内，将 left 更新为 index + 1。
- 更新哈希表中该字符的位置为 right。
- 更新 max_len = max(max_len, right - left + 1)。

示例：s = "abcabcbb"

初始化 left=0, max_len=0, char_index={}
i=0: s[0]='a' 不在窗口内，记录 {'a':0}, max_len=1
i=1: s[1]='b' 不在窗口内，记录 {'a':0, 'b':1}, max_len=2
i=2: s[2]='c' 不在窗口内，记录 {'a':0, 'b':1, 'c':2}, max_len=3
i=3: s[3]='a' 上次出现在索引0，且0>=left(0)，所以 left=0+1=1，更新 'a':3, 当前窗口[1,3]长度3
i=4: s[4]='b' 上次出现在1，且1>=left(1)，所以 left=1+1=2，更新 'b':4, 窗口[2,4]长度3
i=5: s[5]='c' 上次出现在2，且2>=left(2)，所以 left=2+1=3，更新 'c':5, 窗口[3,5]长度3
i=6: s[6]='b' 上次出现在4，且4>=left(3)，所以 left=4+1=5，更新 'b':6, 窗口[5,6]长度2
i=7: s[7]='b' 上次出现在6，且6>=left(5)，所以 left=6+1=7，更新 'b':7, 窗口[7,7]长度1
最终 max_len=3

这个算法只需遍历一次字符串，时间复杂度 O(n)，空间复杂度 O(字符集大小)。

5. 总结

最长不重复子串问题是一个典型的滑动窗口应用，核心是维护一个不重复的窗口，并在重复出现时调整窗口左边界。优化后的解法（使用哈希表记录位置）能一次遍历得到结果，是面试中常见的高效解法。

最长不重复子串（Longest Substring Without Repeating Characters）最长不重复子串是一个经典的字符串算法问题，其描述为：给定一个字符串，找出其中不含有重复字符的最长子串的长度。 1. 问题描述假设输入字符串为 "abcabcbb"，我们需要找到其中最长的连续子串，使得这个子串中的字符互不重复。对于这个例子，答案应该是 3，因为最长的不重复子串是 "abc"。输入 : 一个字符串 s (例如 "abcabcbb") 输出 : 一个整数，表示最长不重复子串的长度 2. 从直观思路出发我们先从一个最朴素的想法开始。要找到一个不重复的子串，最容易想到的方法是枚举所有可能的子串，然后检查其中是否有重复字符。具体步骤：用两个指针（或索引） i 和 j 表示子串的起始和结束位置。对于每个起始位置 i ，将 j 从 i 开始往后移动，每次加入一个新字符，并检查新字符是否在子串中出现过。如果没有重复，就更新最大长度；如果重复了，就停止移动 j ，然后移动 i 到下一位。这种方法的时间复杂度约为 O(n³)，因为检查是否有重复字符需要 O(n) 时间，加上两层循环枚举，效率很低。我们需要优化。 3. 使用滑动窗口优化我们可以用“滑动窗口”的思想来避免不必要的检查。滑动窗口是表示当前不重复子串的一个区间 [ left, right ]。我们通过一个集合来记录窗口中已有的字符，这样就能在 O(1) 时间内判断新字符是否在窗口中。具体步骤：初始化一个空集合 char_set 用来存放窗口中的字符。初始化两个指针： left = 0 和 right = 0 ，表示窗口的左右边界（左闭右开）。初始化一个变量 max_len = 0 记录答案。遍历字符串，每次将 s[right] 加入窗口：如果 s[right] 不在 char_set 中，说明可以扩展窗口，将其加入集合，然后更新 max_len = max(max_len, right - left + 1) ，接着将 right 右移。如果 s[right] 已经在 char_set 中，说明出现了重复，这时我们需要移动 left 指针，直到窗口中不包含这个重复字符为止。每次移动 left 时，从集合中移除 s[left] ，然后 left++ 。重复上述过程直到 right 到达字符串末尾。示例：s = "abcabcbb" 窗口变化过程： [ a ] -> 长度 1 [ a,b ] -> 长度 2 [ a,b,c ] -> 长度 3 加入 a 时重复，移动 left 直到移除之前的 a，窗口变为 [ b,c,a ] -> 长度 3 加入 b 重复，移动 left 移除 b，窗口变为 [ c,a,b ] -> 长度 3 加入 c 重复，移动 left 移除 c，窗口变为 [ a,b,c ] -> 长度 3 加入 b 重复，移动 left 直到移除 b，窗口变为 [ c,b ] -> 长度 2 加入 b 重复，移动 left 移除 b，窗口变为 [ b ] -> 长度 1 最长长度始终为 3。这种方法将时间复杂度降为 O(n)，因为每个字符最多被加入和移除集合一次。 4. 进一步优化：使用哈希表记录位置上面用集合的方法，在出现重复时需要不断移动 left 直到移除重复字符。这一步可以优化，如果我们用一个哈希表记录每个字符最近出现的位置，那么当遇到重复字符时，我们可以直接让 left 跳转到重复字符上次出现位置的下一位，而不是一步步移动。具体步骤：初始化一个哈希表 char_index ，键是字符，值是该字符最近一次出现的索引。初始化 left = 0 ， max_len = 0 。遍历字符串，对于每个索引 right ：如果当前字符 s[right] 在哈希表中，并且其上次出现位置 index 大于等于 left ，说明重复出现在当前窗口内，将 left 更新为 index + 1 。更新哈希表中该字符的位置为 right 。更新 max_len = max(max_len, right - left + 1) 。示例：s = "abcabcbb" 初始化 left=0, max_ len=0, char_ index={} i=0: s[ 0]='a' 不在窗口内，记录 {'a':0}, max_ len=1 i=1: s[ 1]='b' 不在窗口内，记录 {'a':0, 'b':1}, max_ len=2 i=2: s[ 2]='c' 不在窗口内，记录 {'a':0, 'b':1, 'c':2}, max_ len=3 i=3: s[ 3]='a' 上次出现在索引0，且0>=left(0)，所以 left=0+1=1，更新 'a':3, 当前窗口[ 1,3 ]长度3 i=4: s[ 4]='b' 上次出现在1，且1>=left(1)，所以 left=1+1=2，更新 'b':4, 窗口[ 2,4 ]长度3 i=5: s[ 5]='c' 上次出现在2，且2>=left(2)，所以 left=2+1=3，更新 'c':5, 窗口[ 3,5 ]长度3 i=6: s[ 6]='b' 上次出现在4，且4>=left(3)，所以 left=4+1=5，更新 'b':6, 窗口[ 5,6 ]长度2 i=7: s[ 7]='b' 上次出现在6，且6>=left(5)，所以 left=6+1=7，更新 'b':7, 窗口[ 7,7 ]长度1 最终 max_ len=3 这个算法只需遍历一次字符串，时间复杂度 O(n)，空间复杂度 O(字符集大小)。 5. 总结最长不重复子串问题是一个典型的滑动窗口应用，核心是维护一个不重复的窗口，并在重复出现时调整窗口左边界。优化后的解法（使用哈希表记录位置）能一次遍历得到结果，是面试中常见的高效解法。