题意
给定一个字符串,找出没有重复字符的最长子串;
解答
一般这种重复字符串、重复数字都优先考虑滑动窗口(使用左右边界两个指针实现。
对于滑动窗口简单说明:(l
是左边界,r
是右边界)
- 滑动窗口初始位置
l=r=0
; - 滑动窗口动态变化的,大小为
r-l+1
; - 滑动窗口
l <= r
; - 滑动窗口左右边界都向右滑动;
针对找出没有重复字符的最长子串这种问题,最根本是找到最大的滑动窗口,且最大的滑动窗口中没有重复的字符,遵循的原则是如果即将进入滑动窗口右边界字符已经存在滑动窗口中,为了保证无重复字符串,则滑动窗口左边界要向右移动到已经存在字符的下一个位置,这样才能使将要进入的字符进入滑动窗口;
针对字符串pwwkew
为例:
-
初始状态,滑动窗口左右边界都指向0,
l->0, r->0
-
判断右边界
p
是否已经存在滑动窗口hash表中,不存在则加入hash表;
-
滑动窗口右指针向右移动,
r->1
,判断右边界w
是否已经存在滑动窗口hash表中,不存在则加入hash表;
-
滑动窗口右指针向右移动,
r->2
,判断右边界w
是否已经存在滑动窗口hash表中,hash表中已经存在,则左边界为hash表中已经存在字符的位置+1,即l=max(l, pos[s[r]+1])
(注意:左边界不能左移),然后再更新已经存在字符的位置pos[s[r]]=r
;
-
滑动窗口右指针向右移动,
r->3
,判断右边界k
是否已经存在滑动窗口hash表中,不存在则加入hash表;
-
滑动窗口右指针向右移动,
r->4
,判断右边界e
是否已经存在滑动窗口hash表中,不存在则加入hash表;
-
滑动窗口右指针向右移动,
r->5
,判断右边界w
是否已经存在滑动窗口hash表中,hash表中已经存在,则左边界为hash表中已经存在字符的位置+1,即l=max(l, pos[s[r]+1])
(注意:左边界不能左移),然后再更新已经存在字符的位置pos[s[r]]=r
;
-
每次迭代选取最大的滑动窗口大小
r-l+1
;
代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0;
unordered_map<char, int> pos;
for(int l = 0, r = 0; r < s.length(); ++ r) {
if (pos.count(s[r])){
l = max(l, pos[s[r]]+1);
}
pos[s[r]] = r;
res = max(res, r-l+1);
}
return res;
}
};
网友评论