漫画：滑动窗口系列，无重复字符的最长子串

在上一节中&＃xff0c;我们使用双端队列完成了滑动窗口的一道颇为困难的题目&＃xff0c;以此展示了什么是滑动窗口。在本节中我们将继续深入分析&＃xff0c;探索滑动窗口题型一些具有模式性的解法。

01

滑动窗口介绍

对于大部分滑动窗口类型的题目&＃xff0c;一般是考察字符串的匹配。比较标准的题目&＃xff0c;会给出一个模式串B&＃xff0c;以及一个目标串A。然后提出问题&＃xff0c;找到A中符合对B一些限定规则的子串或者对A一些限定规则的结果&＃xff0c;最终再将搜索出的子串完成题意中要求的组合或者其他。

比如&＃xff1a;给定一个字符串 s 和一个非空字符串 p&＃xff0c;找到 s 中所有是 p 的字母异位词的子串&＃xff0c;返回这些子串的起始索引。

又或者&＃xff1a;给你一个字符串 S、一个字符串 T&＃xff0c;请在字符串 S 里面找出&＃xff1a;包含 T 所有字母的最小子串。

再如&＃xff1a;给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

都是属于这一类的标准题型。而对于这一类题目&＃xff0c;我们常用的解题思路&＃xff0c;是去维护一个可变长度的滑动窗口。无论是使用双指针&＃xff0c;还是使用双端队列&＃xff0c;又或者用游标等其他奇技淫巧&＃xff0c;目的都是一样的。   

Now&＃xff0c;我们通过一道题目来进行具体学习&＃xff1a;

02

第3题&＃xff1a;无重复字符的最长子串

第3题&＃xff1a;给定一个字符串&＃xff0c;请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"

输出: 3 

解释: 因为无重复字符的最长子串是 "abc"&＃xff0c;所以其长度为 3。

示例 2:

输入: "bbbbb"

输出: 1

解释: 因为无重复字符的最长子串是 "b"&＃xff0c;所以其长度为 1。

示例 3:

输入: "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke"&＃xff0c;所以其长度为 3。

请注意&＃xff0c;你的答案必须是 子串 的长度&＃xff0c;"pwke" 是一个子序列&＃xff0c;不是子串。

03

题解分析

直接分析题目&＃xff0c;假设我们的输入为“abcabcbb”&＃xff0c;我们只需要维护一个窗口在输入字符串中进行移动。如下图&＃xff1a;

本题基本就到这里。最后要说的&＃xff0c;一般建议如果要分析一道题&＃xff0c;我们要压缩压缩再压缩&＃xff0c;抽茧剥丝一样走到最后&＃xff0c;尽可能的完成对题目的优化。不一定非要自己想到最优解&＃xff0c;但绝对不要局限于单纯的完成题目&＃xff0c;那样将毫无意义&＃xff01;

最后&＃xff0c;原创文章实在不易...希望大家可以帮忙转发~不胜感激~&＃xff08;记得打卡&＃xff09;

1. 全栈架构之打包推荐【建议收藏&＃xff0c;常读】

2. 探讨确保消息消费幂等性的几种方式

3. 分布式系统中Session共享的常用方案

4. Java语言“坑爹”排行榜TOP 10

5. 我是一个Java类&＃xff08;附带精彩吐槽&＃xff09;

6. mysql索引失效&＃xff0c;差点我的工作凉了

7. 既生synchronized&＃xff0c;何生volatile&＃xff1f;

8. 微服务一直火&＃xff0c;为什么服务化要搞懂&＃xff1f;

9. MySQL的COUNT语句&＃xff0c;不简单&＃xff01;

10. 漫画&＃xff1a;HashSet和TreeSet实现与原理

扫码二维码关注我

·end·

—如果本文有帮助&＃xff0c;请分享到朋友圈吧—

我们一起愉快的玩耍&＃xff01;

你点的每个赞&＃xff0c;我都认真当成了喜欢