总结

liweiwei1419 ... 2021-12-24 滑动窗口
  • 滑动窗口
About 3 min

# 阶段总结

  • 这两道问题一道找不重复的最长子串的长度,另一道找长度大于等于 target 的连续子数组的最短的长度,滑动窗口算法使得枚举子串、连续子数组的数量级降低到 O(N)O(N)
  • 我们在代码的注释当中有写:
    • 第 3 题:循环不变量:区间 [left..right] 内没有重复元素,因此计算区间长度的时候使用 right - left + 1
    • 第 209 题:循环不变量:nums[left..right) >= s,因此计算区间长度的时候使用 right - left

「循环不变量」是人为的定义,大家不必和我一样,用左闭右开区间只是为了在计算区间长度的时候使用 right - left 而不用加 11,没有特别的用意。不知道大家对「循环不变量」有没有兴趣,以后我们可以再写一期「循环不变量」。

  • 大家可以再瞄一眼,取最大值和最小值的位置不一样。

使用滑动窗口算法的细节比较多,但是完全不用记忆,其实凭着对题目的理解,只要逻辑上的严密的,就不难写对代码。


  • 想清楚「为什么可以使用滑动窗口」是更重要的;通常这样的原因基于题目中给出的关键信息,例如:「连续」「正整数」,并且题目 只问最值,并不要求得到的解,或者只要求写出一个解;
  • 先思考暴力解法,再思考暴力解法哪一些解没有必要考虑,得到滑动窗口的解法就会比较自然。「力扣」上还有一类以「双指针」为标签的问题也是这样的思路,它们都少考虑了很多「暴力解法」需要考虑的情况,使得时间复杂度将到了线性级别;
  • 注意题目中通常会有:输入字符串「只包含小写字母」「只包含大写字母」等信息,可以使用数组代替哈希表,它们的作用都是计算区间内字符或者数字的频数,以简化编码;
  • 在做题的过程需要留意自己设置的 leftright 的含义,什么时候区间的长度是 right - left,什么时候是 right - left + 1 需要非常清楚,这件事情叫做:在编码的过程中保持了「循环不变量」;
  • 有一些问题变量名比较多,在起变量名的时候需要做到表意清晰、见名知义,才不会让自己绕晕。

# 两道非常重要的例题以及练习

由于篇幅的原因,下面我们给出例题和练习,大家可以在「力扣」对应问题的官方题解里下面看到这两道问题的视频题解,全是我讲的。

这两道问题的细节比较多,并且以它们为基础的问题也有不少。相信大家把它们都做完,对这一类问题的理解会有较大的提升

# 关于如何学习题解区他人的代码

我在「力扣」的题解区学习这些问题的时候,遇到不明白的地方,就会在程序里面写上一些打印输出语句,就像下面这样。很多时候,程序的逻辑就会变得很清晰。

理解了思路以后,我会自己再写一遍。

# 总结

滑动窗口很多书上都没有单独列出来说,在我看来,它只是一个技巧,它只能解决特定的问题。所以大家只要花时间用心练习,是一定可以掌握的,我们加油!

Last update: December 24, 2021 11:49
Contributors: liweiwei1419