3. 无重复字符的最长子串
3 min
题目
思路
使用滑动窗口和哈希集合维护无重复字符区间。
正确性在于：当右指针遇到重复字符时，左指针移动到重复字符上次出现位置的下一位，确保窗口内始终无重复。该操作不会遗漏最优解，因为窗口移动过程中已覆盖所有可能子串的结束位置。
- Step 1: 初始化左指针left=0和空字符集合charSet
- Step 2: 右指针right遍历字符串每个字符
- Step 3: 若当前字符在集合中，循环移除左指针字符并右移left
- Step 4: 将当前字符加入集合并更新最大长度res
- Step 5: 返回最终结果res
复杂度
- 时间复杂度: ，每个字符最多被加入和移出集合各一次
- 空间复杂度: ，字符集大小固定（ASCII最多128个）
代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 滑动窗口核心逻辑和Java版本完全一致
unordered_set<char> charSet; // 去重集合，对应Java的HashSet
int res = 0; // 存储最长无重复子串的长度
int left = 0; // 滑动窗口左指针
// right作为右指针，遍历字符串的每个字符
for (int right = 0; right < s.size(); ++right) {
char ch = s[right]; // 当前右指针指向的字符
// 如果集合中已有当前字符，不断收缩左边界，直到移除重复字符
while (charSet.find(ch) != charSet.end()) {
charSet.erase(s[left]); // 移除左指针指向的字符
left++; // 左指针右移
}
// 将当前字符加入集合
charSet.insert(ch);
// 更新最长子串长度（当前窗口长度：right - left + 1）
res = max(res, right - left + 1);
}
return res;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 滑动窗口核心逻辑和Java版本完全一致
unordered_set<char> charSet; // 去重集合，对应Java的HashSet
int res = 0; // 存储最长无重复子串的长度
int left = 0; // 滑动窗口左指针
// right作为右指针，遍历字符串的每个字符
for (int right = 0; right < s.size(); ++right) {
char ch = s[right]; // 当前右指针指向的字符
// 如果集合中已有当前字符，不断收缩左边界，直到移除重复字符
while (charSet.find(ch) != charSet.end()) {
charSet.erase(s[left]); // 移除左指针指向的字符
left++; // 左指针右移
}
// 将当前字符加入集合
charSet.insert(ch);
// 更新最长子串长度（当前窗口长度：right - left + 1）
res = max(res, right - left + 1);
}
return res;
}
};