Completed
标签
相关企业
难度
这里首先区分一下常见的“子”的概念
类型 | 名称 | 连续性 |
数组 | 子数组 | 连续 |
数组 | 子序列 | 不一定连续 |
字符串 | 子串 | 连续 |
字符串 | 子序列 | 不一定连续 |
当题目中出现子数组或子串时，这时不能改变原数组或字符串的顺序，通常可以使用滑动窗口解决。
当出现子序列时，可以改变原数组或字符串的顺序
定长滑动窗口
题目往往要求在数组或字符串中找到符合xxx要求的，长度为k的子数组或子串，通过维护一个长度为k的窗口，不断向右移动窗口的同时判断是否符合题目要求，伪代码如下
定长滑动窗口 | 属性 | 评级 |
基础 | 4 | |
基础 | 3 | |
基础 | 3 | |
基础 | 3 | |
基础 | 3 | |
基础 | 4 | |
基础 | 4 | |
基础 | 4 | |
进阶 | 4 | |
进阶 | 4 | |
进阶 | 4 | |
进阶 | 5 | |
进阶 | 4 | |
进阶 | 4 | |
进阶 | 3 | |
进阶 | 6 | |
进阶 | 5 | |
进阶 | 6 | |
进阶 | 4 | |
进阶 | 4 |
不定长滑动窗口
求子数组/子串：最长长度
题目往往要求找到符合xxx要求的子数组或子串的最大长度
xxx要求比如：某个字符出现次数不能超过2次/不能有连续的2个xxx
总之就是越短越符合要求，求的是最长符合要求的长度，伪代码如下：
求子数组/子串：最长长度 | 属性 | 评级 |
基础 | 5 | |
基础 | 2 | |
基础 | 6 | |
基础 | 5 | |
基础 | 5 | |
基础 | 5 | |
基础 | 5 | |
基础 | 5 | |
基础 | 5 | |
基础 | 5 | |
基础 | 5 | |
进阶 | 2 | |
进阶 | 5 | |
进阶 | 6 | |
进阶 | 5 | |
进阶 | 6 |
求子数组/子串：最短长度
题目往往要求找到符合xxx要求的子数组或子串的最短长度
xxx要求比如：子串/子数组总和要大于target等等
总之就是越长越符合要求，求的是最短符合要求的长度，伪代码如下：
- 注意和《求最长长度》不同的是：更新res要在while循环里，因为while循环会不断循环直至不符合要求，如果在while循环外更新，需要额外复杂的判断
求子数组/子串：最短长度 | 属性 | 评级 |
基础 | 5 | |
基础 | 2 | |
进阶 | 7 | |
进阶 | 6 | |
进阶 | 6 | |
进阶 | 7 |
求子数组/子串：数量
- 窗口越短越合法
在《求子数组/子串：最长长度》while循环结束后，此时[left,right]窗口内的数组一定是合法的，我们要求（以right为右端点时，符合要求的子数组/子串的数量），因为窗口越短越合法，所以[left,right]，[left+1,right]，[left+2,right]…[right,right]都是合法的，一共right-left+1个数组都是合法的，所以这里的res更新变为res+=right-left+1，然后继续右移右端点right，伪代码如下：
求子数组/子串：数量（窗口越短越合法） | 属性 | 评级 |
基础 | 5 | |
基础 | 1 | |
进阶 | 5 | |
进阶 | 6 | |
进阶 | ㅤ |
- 窗口越长越合法
在《求子数组/子串：最短长度》while循环结束后，此时[left,right]窗口内的数组一定是不合法的，我们要求（以right为右端点时，符合要求的子数组/子串的数量），因为窗口越长越合法，所以[left-1,right]，[left-2,right]，[left-3,right]…[0,right]都是合法的，一共left个数组都是合法的，所以这里的res更新变为res+=left，然后继续右移右端点right，伪代码如下：
求子数组/子串：数量：窗口越长越合法 | 属性 | 评级 |
基础 | 5 | |
基础 | 5 | |
基础 | 3 | |
基础 | 3 | |
进阶 | 6 | |
进阶 | 6 |
- 恰好型滑动窗口
例如要求有多少个子数组的和恰好等于target
- 先求出≥target的子数组数量num1，再求出≥target+1的子数组数量num2，最终结果就是num1-num2
- 或者先求出≤target的子数组数量num1，再求出≤target+1的子数组数量num2，最终结果就是num1-num2
以上两种方法都可以通过调用两次不定长滑动窗口实现
求子数组/子串：数量：恰好型滑动窗口 | 属性 | 评级 |
基础 | 5 | |
基础 | 5 |
