思路分析:
- 使用双指针
i
和j
表示子串的起始位置和结束位置。 - 遍历字符串
s
,对于每个字符:- 如果字符不在
hash
中,将其加入hash
,同时更新最长子串的长度result
。 - 如果字符已经在
hash
中,说明有重复字符出现,需要移动i
指针,并从hash
中移除s[i]
,直到没有重复字符。
- 如果字符不在
- 最终返回
result
,即最长无重复字符子串的长度。
class Solution {
public:
// 函数用于计算最长无重复字符子串的长度
int lengthOfLongestSubstring(string s) {
// 创建一个无序集合 hash 用于存储字符
unordered_set<char> hash;
// 字符串 s 的长度
int n = s.size();
// 初始化两个指针 i 和 j,表示子串的起始位置和结束位置
int i, j;
// 用于存储最终的结果,即最长无重复字符子串的长度
int result = 0;
// 使用双指针法,i 指向子串的起始位置,j 指向子串的结束位置
for (i = 0, j = 0; j < n;) {
// 如果当前字符 s[j] 不在 hash 中,说明可以将其加入子串
if (hash.insert(s[j]).second) {
// 更新结果为当前子串的长度和之前的结果中的较大值
result = max(result, j - i + 1);
// 移动 j 指针到下一个位置
j++;
} else {
// 如果当前字符已经在 hash 中,说明有重复字符出现
// 需要移动 i 指针,同时从 hash 中移除 s[i]
while (!hash.insert(s[j]).second) {
hash.erase(s[i++]);
}
// 移动 j 指针到下一个位置
j++;
}
}
// 返回最终的结果
return result;
}
};