题目
给定一个字符串 s ,请你找出其中不含有重复字符的最长子串的长度
在函数中实现要求
规则示例
规则:
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
解题分析
解此题最常用的解法就是滑动窗口
那么我们首先来理解什么是滑动窗口
我们以字符串:abcdadek举例说明
如果用肉眼去找其中最长的子串,我们会从左到右依次来看
第一次寻找:
开始位置:a(索引0)
得到无重复子串为:abcd(出现重复时停止,重复出现索引位置4)
长度为:无重复结束位置(3) - 开始位置(0) + 1 = 4
第二次寻找:
开始位置:b(索引1)为上一次重复的最左侧a索引0 + 1 = 1
得到无重复子串为:bcda(出现重复时停止,重复出现索引位置5)
长度为:无重复结束位置(4) - 开始位置(1) + 1 = 4
第三次寻找:
开始位置:a(索引4)为上一次重复的最左侧d索引3 + 1 = 4
得到无重复子串为:adek(字符串检查结束停止)
长度为:无重复结束位置(7) - 开始位置(4) + 1 = 4
第三次寻找是一个关键点
第三次的开始位置是索引为4的a,我们忽略了索引2的c和索引3的d
是因为 cda 和 da 不可能比第二次的bcda还要长,他们都是bcda的子串而已
所以从第三次我们可以看出
每次开始的位置:是上一次重复的最左侧字符的索引 + 1
通过以上的分析,我们可以看出滑动窗口方法,其实就是
最左侧索引位置 和 最右侧索引位置 决定的一个窗口区间
left 和 right 两个值的变化决定了“窗口的范围和区域”
就仿佛在滑动一个隐形窗口一样
这个窗口里面包裹的内容就是我们想要的内容
从左到右第一次找不重复子串
从左到右第二次找不重复子串
从左到右第三次找不重复子串
通过我们的分析我们得出一些有用的信息
1.记录最左侧开始位置的变量left
2.记录最右侧的位置的变量right
3.每次发现重复元素后,left的变化规律是变为前方重复元素的后一位(关键规律)
4.用right - left + 1就可以得到满足条件的子串的长度
分步解题
第一步:声明left和right变量
第二步:思考如何用当前遍历的元素和之前的元素做比较?
我们得出一些有用的信息
1.记录最左侧开始位置的变量left
2.记录最右侧的位置的变量right
3.每次发现重复元素后,left的变化规律是变为前方重复元素的后一位(关键规律)
4.用right - left + 1就可以得到满足条件的子串的长度
前两点我们已经在第一步中完成了,要实现第三点,我们需要每次遍历时把当前索引对应的字符和之前位置的字符进行比较,判断是否相同,那么我们完全可以在每次遍历时用一个容器把遍历过的字符和它的位置记录下来,方便后之后的字符进行比较,并且快速获取位置信息!
第三步:如果重复,改变 left 的位置
我们已经有了 left 和 right ,还有记录了内容和位置的字典
那么我们只需要判断当前遍历的字符是否在字典中存在,如果存在则证明重复了。重复的话我们就需要改变 left 的位置为:前方重复元素的后一位
第四步:用right - left + 1得到长度
从上面的分析我们知道,通过right - left + 1就可以得到当前不重复子串的长度,我们需要获取最长的子串长度,所以我们只需要每次都计算,保留最大值就可以了!
第五步:解决特殊情况,left不能回头,得到最终逻辑
当循环第5次时,由于我们没有处理 left 不能回头,就会造成 left 变为最左侧相同元素B的索引加1,这时left比上一次的值要小,但是我们之前left之所以后移的原因,就是因为前方有重复元素,所以当面对这种特殊情况是,我们应该保证 left 的值不能左移
最终实现
总结
找出字符串中不含有重复字符的最长子串的长度的关键解法
1.记录最左侧开始位置的变量left
2.记录最右侧的位置的变量right
3.每次发现重复元素后,left的变化规律是变为前方重复元素的后一位(关键规律)
4.用right - left + 1就可以得到满足条件的子串的长度
5.用字典容器存储最后出现的相同字符的值和索引
6.left不能回头
END