【完虐算法系列】「字符串 – 滑动窗口」复盘总结

穿插一句,今天文末再送书哈...

回归正题:

两点原因,第一点就是有读者说过去文章太长,是否可以考虑截取出来,分类讨论。这一点我是有考虑的,事实上本身文章已经是一个类别了,比如说动态规划,整个介绍超过万字,自我感觉才把一个问题描述的比较清楚。所以,后面考虑再细分,使得想要表述的问题更加调理清楚,可读性更强。

另外一点原因呢,就是关于文章页面展示。也是关于一个可读性的方面,这个是真真切切花了将近一个月搞的一个事情。就是重新打理了一个网站(,感觉还是比较漂亮的,每天都要看几眼、、哈哈)。

这中间还有人问到为什么域名起这样的一个名字,还穿插着数字,咱们还是后面有空在说说(later。。。)

今天咱们一起要讨论的是关于「字符串」的第一块内容。

字符串 - 滑动窗口

今天再把整个的刷题脑图放出来,前面的已经细化,后面一块一块逐渐会整理出来。

可以看在整个大的脑图当中「字符串 - 滑动窗口」这一块。

【完虐算法系列】「字符串 – 滑动窗口」复盘总结

上面是整个 LeetCode 算法刷题计划,图中只细化了二叉树、动态规划和字符串相关理论分析和题目的讲解。所以,没有加入的同学们可以私信我,即使现在没有计划刷题的也可以加入进来,当个看客也不错,身处互联网,迟早会用到。

之前说到过,「字符串」这一块会出 10 篇复盘总结,今天是第一篇「字符串 - 滑动窗口」

「字符串 - 滑动窗口」这一块咱们安排了四个问题,准备用这四个问题将滑动窗口的使用以及相关题目讨论清楚。

【简单】滑动窗口数字之和(引例)

【中等】567.字符串的排列 https://leetcode-cn.com/problems/permutation-in-string/

【困难】239.滑动窗口最大值 https://leetcode-cn.com/problems/sliding-window-maximum/

【中等】3.无重复字符的最长子串 https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

滑动窗口-引例

滑动窗口算法一般是作用在字符串或者数组上,通过不断的滑动逻辑窗口,在特定窗口大小内进行计算的过程。

滑动窗口的方式可以降低时间复杂度,从而减短计算的执行时间。

引例:比如说在字符串 s="5189623196" 中,窗口大小 w=5,找出每个窗口字符子串的和。

普通的计算方式:每 5 个进行一次求个计算,时间复杂度方面能够达到 O(N^2)。

利用窗口的方式:可很大程度可以减小时间方面的消耗。就拿引例来说,时间复杂度应该是O(N)的线性复杂度。

该案例核心思路是:窗口在每一次的滑动前后,中间元素内容没有改变,仅仅改变的是开头和结尾元素。

即:下一窗口内元素之和 = 上一窗口元素和 - 离开窗口元素值 + 新加入窗口元素值

下面分步骤进行讨论,将最终结果写入到 res 中。

步骤一:直接计算窗口内元素和,res = [29]

【完虐算法系列】「字符串 – 滑动窗口」复盘总结

步骤二:在上一步骤的基础上,减去离开窗口的元素,加上新加入窗口的元素。

【完虐算法系列】「字符串 – 滑动窗口」复盘总结

步骤三:继续在上一步骤的基础上,减去离开窗口的元素,加上新加入窗口的元素

【完虐算法系列】「字符串 – 滑动窗口」复盘总结

相同逻辑继续执行....

步骤六:滑动窗口将最后一个元素包含进来

image-20211019003001596

上述每一步骤中,将 sum 值都添加到最终的结果变量 res 中。

滑动窗口这样的思维方式就很巧妙的进行在窗口的不断移动,进而产生各元素在窗口边界进进出出,利用这一点,在时间复杂度方面进行了一个很大提升!

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zgddzg.html