NOTES · 学习笔记
无重复字符的最长子串:用滑动窗口找出最长连续区间
题目
我们要求无重复字符的最长子串。那么什么是子串?子串就是字符串中连续的一段。
我们看示例 1:输入 s = "abcabcbb",输出 3。
滑动窗口思路
我们创建一个 hashmap 用来记录窗口中的元素,并且需要两个指针牵引着我们去找元素。刚开始,左指针和右指针都等于 0。
当左指针等于 0 时,left 指向第一个元素 a,将它放进窗口中:[a]。left 不移动,right 右移。
此时 right 来到第二个元素 b,没有重复,将它添加进窗口中:[a,b]。left 还是不动。right 继续右移,来到第三个位置,此时指向 c,依旧没有重复,所以窗口现在是 [a,b,c]。此时窗口长度是 3,所以我们记录最大长度 maxLen = 3。
right 继续右移,来到第四个位置,此时 right 指向 a,发现窗口中已经有一个 a 了,说明出现重复。那么我们就要处理左指针:将 left 指向的 a 移出窗口,然后 left 右移,窗口变成 [b,c,a]。现在窗口又变成了没有重复的状态。
之后继续让 right 向右移动,如果出现重复,就继续移动 left,直到窗口重新没有重复。每次窗口没有重复之后,我们都要计算当前窗口的长度,并和之前的 maxLen 比较。
right 负责向右扩大窗口,发现重复后 left 负责向右收缩窗口。
实现代码
当前窗口长度可以用 currentLen = right - left + 1 计算。最后等 right 遍历完整个字符串后,循环结束,maxLen 就是答案。
func lengthOfLongestSubstring(s string) int {
left:=0 //左指针当前位置
maxlen:=0 //最长长度
window:=make(map[byte]int) //窗口用来保存子串
currentlen:=0
for right:=0;right<len(s);right++ { //右指针向右移动
window[s[right]]++ //我们让右指针移动保存当前所有元素进入窗口中
for window[s[right]]>1{ //当窗口中的元素重复时
window[s[left]]-- //我们要让左指针所指的元素剔除
left++ //左指针右移
}
currentlen=right-left+1 //当前长度是要等于窗口中右边减去左边加1,这才是完整个数
if currentlen > maxlen{
maxlen=currentlen //最后我们更新一下当前最大长度
}
}
return maxlen //得出答案
}