3. 无重复字符的最长子串
本帖最后由 Gnomeshgh 于 2025-8-18 16:42 编辑一、题目描述
给定一个字符串 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 由英文字母、数字、符号和空格组成
二、解题思路
（一）暴力解
常规思路遍历所有的子串，并判断该字串中是否包含重复的元素。
首先使用两层循环，外层循环代表字串的起始位置，内层循环判断字串中是否有重复的元素。
使用集合来进行上述操作，首先判读元素是否在集合中，是则结束该子串的判断，否则加入到集合中。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 最后返回的最大字串长度
max_len = 0
# 获取字符串的长度
strlen = len(s)
# 外层循环记录字串的起始位置
for i in range(strlen):
# 当剩余字串的长度无法大于最大子串长度就直接结束循环
if max_len > strlen - i:
break
# 设置一个集合
strset = set()
# 存储当前子串的长度
length = 0
# 内层循环进行子串是否有重复元素的检测
for j in range(i,strlen):
# 该元素不在，则加入到集合中，并且当前子串长度加1，并更新最大子串长度
if s not in strset:
strset.add(s)
length = length + 1
max_len = max(max_len , length)
# 该元素在集合中，就结束该子串的判断，开启下一个子串的判断
else:
break
return max_len</font>
（二）滑动窗口
对暴力解进行优化，举例子
可以看出，每次集合中存在已有的元素，就进行下次循环，在进行下次循环的时子串的起始位置后移一位。然后再次从起始位置开始新的循环。
其中bc很明显是重复操作了。
在第二个a插入之前，集合中是没有重复元素的，结束该子串后，只需要将首位后移一位即可,此时也删除p_front所指元素，因为在第二个a插入之前，集合不存在重复的元素。
然后进行第二个a的判断。
总结一下就是，第一个指针指向子串的首部，第二个指针指向子串的尾部，不断的将尾部插入到集合中，
若插入集合已存在该元素，首先删除p_front所指元素，然后p_front后移一位，尾指针不变。然后依次循环。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 获取字符串长度
s_len = len(s)
# 头指针
p_front = 0
# 尾指针
p_rear = 0
# 记录子串最大值
max_len = 0
# 设计一个空集合
str_set = set()
# 当尾指针大于字符串长度结束循环
while p_rear < s_len:
# 当元素不在集合中插入到集合中，否则头指针后移一位，且删除该元素，删除的是p_front所指的元素，而不是重复的元素
if s not in str_set:
str_set.add(s)
p_rear = p_rear + 1
max_len = max(max_len , p_rear - p_front)
else:
str_set.discard(s)
p_front = p_front + 1
return max_len
再次进行优化
可以看出，w是重复的元素，且还知道第一个w的下标，可以直接移动到第一个w的后一位，这样就可以减少p_front的多次移动，在这个过程中，要删除小于等于第一个w下标的元素。怎么快速知道元素下标那，可以使用哈希表进行完成。使用字典来实现哈希表。
在p_front移动的时候，p_front之前的元素全部无效，因为前面的已经不是子串了。
总结一下就是，判断元素在不在哈希表中，不在则更新哈希表。在则判断是否是有效的（有效就是大于p_front），有效的就更新p_front，且更新哈希表，无效也更新哈希表，
也就是无论怎么样都要更新哈希表。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 哈希字典：用于存储每个字符最后一次出现的索引位置
str_dict = {}
# 记录最长无重复子串的长度，初始化为0
max_len = 0
# 左指针：标记当前窗口的起始位置，初始化为0
p_front = 0
# 右指针遍历字符串，enumerate同时获取索引(p_rear)和字符(char)
for p_rear, char in enumerate(s):
# 核心判断：如果字符已存在于字典中，且上次出现的位置在当前窗口内（>=左指针）
# 说明出现重复，需要移动左指针到重复字符的下一位，确保窗口内无重复
if char in str_dict and p_front <= str_dict:
p_front = str_dict + 1
# 更新当前字符在字典中的最后出现位置为右指针索引
str_dict = p_rear
# 计算当前窗口长度（右指针-左指针+1），并更新最大长度
max_len = max(max_len, p_rear - p_front + 1)
# 返回最长无重复子串的长度
return max_len
要解决“无重复字符的最长子串”问题，可以使用**滑动窗口**算法，通过双指针和哈希表高效地跟踪不重复字符的窗口。以下是详细思路和代码：
### 解决思路
1. **初始化**：
- 左指针 `left = 0`，记录窗口起点。
- 哈希表 `char_map` 存储字符最近一次出现的索引。
- `max_len` 记录最大无重复子串长度。
2. **遍历字符串**（右指针 `right` 从 `0` 开始）：
- 若当前字符 `s` 已存在于 `char_map` 中，**且其上次出现位置在 `left` 右侧**（即在当前窗口内），则将左指针移动到重复字符的下一位：`left = max(left, char_map] + 1)`。
- 更新 `char_map` 中 `s` 的索引为当前 `right`。
- 计算当前窗口长度 `right - left + 1`，并更新 `max_len`。
3. **返回结果**：
- 遍历结束后，`max_len` 即为最长无重复子串的长度。
### 代码实现
def lengthOfLongestSubstring(s: str) -> int:
if not s:
return 0
char_map = {}# 存储字符最后出现的位置
left = 0 # 滑动窗口左边界
max_len = 0 # 记录最大长度
for right in range(len(s)):
# 如果字符已存在且在当前窗口内，移动左指针
if s in char_map:
left = max(left, char_map] + 1)
# 更新字符的最近位置
char_map] = right
# 更新最大长度
current_len = right - left + 1
if current_len > max_len:
max_len = current_len
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 小助理，如未能正确解答您的问题，请继续追问。 有点难！ 我这个怎么样
int maxlen(string s) {
unordered_map<char, int> hash;
int n = s.length();
int res = 0;
int l = 0;//左指针
for (int r = 0; r < n; r++) {//右指针
hash]++;
while (hash] > 1) {//出现重复字符
hash]--;
l++;//右移左指针
}
res=max(res,r-l+1);//记录最大值
}
return res;
} xiaoniugogogo 发表于 2025-8-18 17:32
我这个怎么样
你这个也很巧妙，而且还非常简洁，while还可以在优化一下，可以直接跳到重复的下标的后一位，这样不用每次都判断了。
页:
[1]