class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 哈希集合,记录每个字符是否出现过
unordered_set occ;
int n = s.size();
// 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动
int rk = -1, ans = 0;
// 枚举左指针的位置,初始值隐性地表示为 -1
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格,移除一个字符
occ.erase(s[i - 1]);
}
while (rk + 1 < n && !occ.count(s[rk + 1])) {
// 不断地移动右指针
occ.insert(s[rk + 1]);
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = max(ans, rk - i + 1);
}
return ans;
}
};
问:这段代码我没有找到他是如何判断指针内外有没有重复的字符,运用了什么原理
问: int rk = -1, 他的右指针的初始值是—1,那他的左指针的初始值呢。
问: // 枚举左指针的位置,初始值隐性地表示为 -1
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格,移除一个字符
occ.erase(s[i - 1]);
}
while (rk + 1 < n && !occ.count(s[rk + 1])) {
// 不断地移动右指针
occ.insert(s[rk + 1]);
这个从头到尾我都没见到他是如何判断是否有重复的字符,我只看到了左右指针不停地移动,他这个左右指针是如何协调的呢
无重复字符的最长子串基础题
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
2条回答 默认 最新
- togolife 2021-12-03 20:55关注
- 用的unordered_set判断是否有重复,这个是c++基础库中提供的一个模板。类似set,用来去重
occ.count(s[rk + 1]),判断是否已经存在,如果存在会返回1。不存在返回0 - 左指针就是i,初始值为0
- 比如字符串abcdeaf
左指针i = 0, 右指针rk可以一直累加到4也就是e的位置。然后继续累加会有重复'a',结束右指针的循环。ans = 5
然后左指针i = 1,并删除unordered_set中的a,右指针rk可以继续累加到f位置。ans = 6
然后左指针i = 2,右指针已经到了末尾,不用循环了,此时得到ans 仍然为6
后序移动左指针都是无效操作了,因为不可能再比ans大
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 1无用 - 用的unordered_set判断是否有重复,这个是c++基础库中提供的一个模板。类似set,用来去重
悬赏问题
- ¥15 stata安慰剂检验作图但是真实值不出现在图上
- ¥15 c程序不知道为什么得不到结果
- ¥40 复杂的限制性的商函数处理
- ¥15 程序不包含适用于入口点的静态Main方法
- ¥15 素材场景中光线烘焙后灯光失效
- ¥15 请教一下各位,为什么我这个没有实现模拟点击
- ¥15 执行 virtuoso 命令后,界面没有,cadence 启动不起来
- ¥50 comfyui下连接animatediff节点生成视频质量非常差的原因
- ¥20 有关区间dp的问题求解
- ¥15 多电路系统共用电源的串扰问题