3. 无重复字符的最长子串

Gnomeshgh

一、题目描述

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



示例 1:

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

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

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。


提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

二、解题思路

（一）暴力解

常规思路遍历所有的子串，并判断该字串中是否包含重复的元素。
首先使用两层循环，外层循环代表字串的起始位置，内层循环判断字串中是否有重复的元素。
使用集合来进行上述操作，首先判读元素是否在集合中，是则结束该子串的判断，否则加入到集合中。

1. class Solution:
   
2.     def lengthOfLongestSubstring(self, s: str) -> int:
   
3.         # 最后返回的最大字串长度
   
4.         max_len = 0
   
5.         # 获取字符串的长度
   
6.         strlen = len(s)
   
7. 
   
8.         # 外层循环记录字串的起始位置
   
9.         for i in range(strlen):
   
10. 
    
11.             # 当剩余字串的长度无法大于最大子串长度就直接结束循环
    
12.             if max_len > strlen - i:
    
13.                 break
    
14.             
    
15.             # 设置一个集合
    
16.             strset = set()
    
17.             # 存储当前子串的长度
    
18.             length = 0
    
19.             
    
20.             # 内层循环进行子串是否有重复元素的检测
    
21.             for j in range(i,strlen):
    
22.                 # 该元素不在，则加入到集合中，并且当前子串长度加1，并更新最大子串长度
    
23.                 if s[j] not in strset:
    
24.                     strset.add(s[j])
    
25.                     length = length + 1
    
26.                     max_len = max(max_len , length)
    
27.                 # 该元素在集合中，就结束该子串的判断，开启下一个子串的判断
    
28.                 else:
    
29.                     break
    
30.         return max_len</font>

复制代码

（二）滑动窗口

对暴力解进行优化，举例子




可以看出，每次集合中存在已有的元素，就进行下次循环，在进行下次循环的时子串的起始位置后移一位。然后再次从起始位置开始新的循环。
其中bc很明显是重复操作了。


在第二个a插入之前，集合中是没有重复元素的，结束该子串后，只需要将首位后移一位即可,此时也删除p_front所指元素，因为在第二个a插入之前，集合不存在重复的元素。
然后进行第二个a的判断。

总结一下就是，第一个指针指向子串的首部，第二个指针指向子串的尾部，不断的将尾部插入到集合中，
若插入集合已存在该元素，首先删除p_front所指元素，然后p_front后移一位，尾指针不变。然后依次循环。

1. class Solution:
   
2.     def lengthOfLongestSubstring(self, s: str) -> int:
   
3.         # 获取字符串长度
   
4.         s_len = len(s)
   
5.         # 头指针
   
6.         p_front = 0
   
7.         # 尾指针
   
8.         p_rear = 0
   
9.         # 记录子串最大值
   
10.         max_len = 0
    
11.         # 设计一个空集合
    
12.         str_set = set()
    
13. 
    
14.         # 当尾指针大于字符串长度结束循环
    
15.         while p_rear < s_len:
    
16.             # 当元素不在集合中插入到集合中，否则头指针后移一位，且删除该元素，删除的是p_front所指的元素，而不是重复的元素
    
17.             if s[p_rear] not in str_set:
    
18.                 str_set.add(s[p_rear])
    
19.                 p_rear = p_rear + 1
    
20.                 max_len = max(max_len , p_rear - p_front)
    
21.             else:
    
22.                 str_set.discard(s[p_front])
    
23.                 p_front = p_front + 1
    
24.         return max_len

复制代码

再次进行优化

可以看出，w是重复的元素，且还知道第一个w的下标，可以直接移动到第一个w的后一位，这样就可以减少p_front的多次移动，在这个过程中，要删除小于等于第一个w下标的元素。

怎么快速知道元素下标那，可以使用哈希表进行完成。使用字典来实现哈希表。
在p_front移动的时候，p_front之前的元素全部无效，因为前面的已经不是子串了。
总结一下就是，判断元素在不在哈希表中，不在则更新哈希表。在则判断是否是有效的（有效就是大于p_front），有效的就更新p_front，且更新哈希表，无效也更新哈希表，
也就是无论怎么样都要更新哈希表。

1. class Solution:
   
2.     def lengthOfLongestSubstring(self, s: str) -> int:
   
3.         # 哈希字典：用于存储每个字符最后一次出现的索引位置
   
4.         str_dict = {}
   
5.         # 记录最长无重复子串的长度，初始化为0
   
6.         max_len = 0
   
7.         # 左指针：标记当前窗口的起始位置，初始化为0
   
8.         p_front = 0
   
9.         
   
10.         # 右指针遍历字符串，enumerate同时获取索引(p_rear)和字符(char)
    
11.         for p_rear, char in enumerate(s):
    
12.             # 核心判断：如果字符已存在于字典中，且上次出现的位置在当前窗口内（>=左指针）
    
13.             # 说明出现重复，需要移动左指针到重复字符的下一位，确保窗口内无重复
    
14.             if char in str_dict and p_front <= str_dict[char]:
    
15.                 p_front = str_dict[char] + 1
    
16.             
    
17.             # 更新当前字符在字典中的最后出现位置为右指针索引
    
18.             str_dict[char] = p_rear
    
19.             
    
20.             # 计算当前窗口长度（右指针-左指针+1），并更新最大长度
    
21.             max_len = max(max_len, p_rear - p_front + 1)
    
22.         
    
23.         # 返回最长无重复子串的长度
    
24.         return max_len

复制代码

FishC

要解决“无重复字符的最长子串”问题，可以使用**滑动窗口**算法，通过双指针和哈希表高效地跟踪不重复字符的窗口。以下是详细思路和代码：

### 解决思路
1. **初始化**：
   - 左指针 `left = 0`，记录窗口起点。
   - 哈希表 `char_map` 存储字符最近一次出现的索引。
   - `max_len` 记录最大无重复子串长度。

2. **遍历字符串**（右指针 `right` 从 `0` 开始）：
   - 若当前字符 `s[right]` 已存在于 `char_map` 中，**且其上次出现位置在 `left` 右侧**（即在当前窗口内），则将左指针移动到重复字符的下一位：`left = max(left, char_map[s[right]] + 1)`。
   - 更新 `char_map` 中 `s[right]` 的索引为当前 `right`。
   - 计算当前窗口长度 `right - left + 1`，并更新 `max_len`。

3. **返回结果**：
   - 遍历结束后，`max_len` 即为最长无重复子串的长度。

### 代码实现

1. 
   
2. def lengthOfLongestSubstring(s: str) -> int:
   
3.     if not s:
   
4.         return 0
   
5.     char_map = {}  # 存储字符最后出现的位置
   
6.     left = 0       # 滑动窗口左边界
   
7.     max_len = 0    # 记录最大长度
   
8.    
   
9.     for right in range(len(s)):
   
10.         # 如果字符已存在且在当前窗口内，移动左指针
    
11.         if s[right] in char_map:
    
12.             left = max(left, char_map[s[right]] + 1)
    
13.         # 更新字符的最近位置
    
14.         char_map[s[right]] = right
    
15.         # 更新最大长度
    
16.         current_len = right - left + 1
    
17.         if current_len > max_len:
    
18.             max_len = current_len
    
19.     return max_len
    

复制代码

### 示例解析
以 s = "abcabcbb" 为例：
1. right=0：字符 'a' 加入，窗口为 "a"，长度=1。
2. right=1：字符 'b' 加入，窗口为 "ab"，长度=2。
3. right=2：字符 'c' 加入，窗口为 "abc"，长度=3（最大长度）。
4. right=3：字符 'a' 重复，左指针移动到 1，窗口为 "bca"，长度=3。
5. 后续同理，最终返回最大长度 3。

### 复杂度分析
- **时间复杂度**：O(n)，仅需一次遍历字符串。
- **空间复杂度**：O(字符集大小)，哈希表存储字符索引。

此方法高效且简洁，适用于所有符合题意的输入。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

不二如是

有点难！

xiaoniugogogo

我这个怎么样

1. int maxlen(string s) {
   
2.         unordered_map<char, int> hash;
   
3.         int n = s.length();
   
4.         int res = 0;
   
5.         int l = 0;//左指针
   
6.         for (int r = 0; r < n; r++) {//右指针
   
7.                 hash[s[r]]++;
   
8.                 while (hash[s[r]] > 1) {//出现重复字符
   
9.                         hash[s[l]]--;
   
10.                         l++;//右移左指针
    
11.                 }
    
12.                 res=max(res,r-l+1);//记录最大值
    
13. 
    
14.         }
    
15.         return res;
    
16. }

复制代码

Gnomeshgh

xiaoniugogogo 发表于 2025-8-18 17:32
我这个怎么样

你这个也很巧妙，而且还非常简洁，while还可以在优化一下，可以直接跳到重复的下标的后一位，这样不用每次都判断了。