NOTES · 学习笔记

无重复字符的最长子串:用滑动窗口找出最长连续区间

LeetCode滑动窗口 · 中等约 5 分钟

题目

我们要求无重复字符的最长子串。那么什么是子串?子串就是字符串中连续的一段。

我们看示例 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 //得出答案
}