前置知识：无
滑动窗口：维持左、右边界都不回退的一段范围，来求解很多子数组（串）的相关问题
滑动窗口的关键：找到范围和答案指标之间的单调性关系（类似贪心）（单调性：一段范围变大或变小对答案产生的影响单调）
滑动过程：滑动窗口可以用简单变量或者结构来维护信息
求解大流程：求子数组在每个位置开头或结尾情况下的答案（开头还是结尾在于题目和个人习惯）
题目1.累加和大于等于 target 的最短子数组长度
题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
测试链接
思路
滑动窗口的关键：找到范围和答案指标之间的单调性关系
范围越大，累加和越大
范围右指针向右阔：累加和变大；范围左指针向右阔：累加和变小
滑动过程：滑动窗口可以用简单变量或者结构来维护信息
sum一个变量维护当前窗口的累加和信息
求解大流程：求子数组在每个位置开头或结尾情况下的答案
求在每个位置结尾情况下的答案，右指针不动，左指针不断往右阔，以寻找更短的子数组长度
如果数组中有负数，就没有这个单调性了，可以用 前缀和 的方法来做
答案
func minSubArrayLen(target int, nums []int) int {
n := len(nums)
ans := n + 1 // math.MaxInt
l := 0
sum := 0
for r := 0; r < n; r++ {
sum += nums[r]
for sum >= target {
ans = min(ans, r-l+1)
sum -= nums[l]
l++
}
}
if ans == n+1 {
return 0
}
return ans
}复杂度
- 时间复杂度：，
l、r都不回退 - 空间复杂度：
题目2.无重复字符的最长子串
题目描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
提示：
0 <= s.length <= 5 * 10^4s由英文字母、数字、符号和空格组成
测试链接
思路
滑动窗口的关键：找到范围和答案指标之间的单调性关系
单调性不明显，可以理解为越往右阔，越能找到更长的无重复字符子串
范围右指针向右阔：更新右指针位置字符的最晚出现下标
滑动过程：滑动窗口可以用简单变量或者结构来维护信息
last一个哈希表（用数组表示）维护当前右指针遍历过的字符最晚出现下标的信息
求解大流程：求子数组在每个位置开头或结尾情况下的答案
求在每个位置结尾情况下的答案，右指针不动，左指针通过
last哈希表跳跃式往右阔
答案
func lengthOfLongestSubstring(s string) int {
n := len(s)
ans := 0
l := 0
last := [256]int{}
for i := range last {
last[i] = -1 // 没开始遍历，所有字符都最早出现在 -1 处
}
for r := 0; r < n; r++ {
// l 保持当前位置或 r 处字符的上一次出现位置 + 1
l = max(l, last[s[r]]+1)
last[s[r]] = r
ans = max(ans, r-l+1)
}
return ans
}复杂度
- 时间复杂度：，
l、r都不回退 - 空间复杂度：，256 长度的数组
题目3.最小覆盖子串
题目描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
提示：
m == s.lengthn == t.length1 <= m, n <= 105s和t由英文字母组成
进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？
测试链接
思路
滑动窗口的关键：找到范围和答案指标之间的单调性关系
范围越大，越容易还清
范围右指针向右阔：还欠款（可能有效还款，可能还了不欠的字符）；
范围左指针向右阔：取回多给的字符（为了最小长度）
滑动过程：滑动窗口可以用简单变量或者结构来维护信息
cnts一个哈希表（用数组表示）维护当前窗口中各个字符欠款数量的信息；
debt欠款总额，不用遍历cnts就能判断是否仍然欠款
求解大流程：求子数组在每个位置开头或结尾情况下的答案
求在每个位置结尾情况下的答案，右指针不动，左指针往右阔，拿回多给的字符
答案
func minWindow(s string, t string) string {
n := len(s)
// 欠债总额
debt := len(t)
if n < debt {
return ""
}
// 欠债表：负数就是欠债，正数就是多给的
cnts := [256]int{}
for i := 0; i < debt; i++ {
cnts[t[i]]--
}
l := 0
start := 0
size := n + 1 // math.MaxInt
for r := 0; r < n; r++ {
cnts[s[r]]++
if cnts[s[r]] <= 0 {
// 有效还款
debt--
}
if debt == 0 { // 还清
for cnts[s[l]] > 0 {
cnts[s[l]]-- // 拿回多给的
l++
}
if r-l+1 < size {
size = r - l + 1
start = l
}
}
}
if size == n+1 {
return ""
}
return s[start : start+size]
}复杂度
- 时间复杂度：，
l、r都不回退 - 空间复杂度：，256 长度的数组
题目4.加油站
题目描述
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
测试链接
思路
滑动窗口的关键：找到范围和答案指标之间的单调性关系
能跑到下个加油站就跑，跑不到就尝试下一个位置（当前跑到了哪里的信息会保留）
范围右指针向右阔：跑到下个加油站；
范围左指针向右阔：跑不到了，尝试下一个位置
滑动过程：滑动窗口可以用简单变量或者结构来维护信息
sum当前窗口累加和（油量）；
size当前窗口大小，方便看是否绕了一圈，和记录当前l跑到了哪个位置
求解大流程：求子数组在每个位置开头或结尾情况下的答案
求在每个位置开头情况下的答案，看看能不能饶一圈
还有 贪心的思路，但不是本节的重点
贪心思路：
- 左边界的更新：如果发现
[l, r]范围内的sum<0，即油不够的情况，左边界可以直接更新成r+1，sum和size置 0。- 因为对于任意的
l < i < r，一定满足[l, i]范围内的sum ≥ 0（不然右边界不可能扩过来），那也就意味着，从(l, r]范围内的任意位置出发，到r位置的sum都小于 0，左边界l可以直接更新成r+1，而不用一点点更新l、size和sum
- 因为对于任意的
- 右边界的更新：右边界实际不用走一圈多，右边界走到最后一个加油站的位置即可
- 根据题意，只有两种可能：要么不存在合法的加油站，要么存在唯一的加油站：
- ①是否存在合法的加油站：只需要右边界从左到右移动的时候，计算一个净油量数组的整体的累加和，判断它是否大于等于零，如果是，一定存在合法的加油站，且唯一，如果否，返回 -1。
- ②既然存在合法的加油站，而你的右边界又来到了数组中的最后一个加油站，此时右边界不用再重新回到开头的地方来跑第二圈，因为根据①，右边界来到第一圈最后一个加油站时，就已经知道了是否存在满足题意的加油站了，如果净油量数组总和大于零，
l就是满足题意的左边界，不可能出现“r在第二圈跑着跑着，发现l不满足题意，而(l, end]中又有一个满足题意的加油站”的情况，这一点可以通过第 1 点优化得出的结论证明。
答案
func canCompleteCircuit(gas []int, cost []int) int {
n := len(gas)
// 当前窗口累加和
sum := 0
r := 0
// 窗口大小
size := 0
for l := 0; l < n; l++ {
for sum >= 0 {
if size == n { // 绕了一圈了
return l
}
// 将 r 加入到窗口中
r = (l + size) % n
size++
sum += gas[r] - cost[r]
}
// 油量不够了：从 l 出发绕不了一圈，尝试下一个 l 位置
size--
sum -= gas[l] - cost[l]
}
return -1
}复杂度
- 时间复杂度：，
l转一圈，r最多转一圈多点 - 空间复杂度：
题目5.替换子串得到平衡字符串
题目描述
有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。
给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
请返回待替换子串的最小可能长度。
如果原字符串自身就是一个平衡字符串，则返回 0。
提示：
1 <= s.length <= 10^5s.length是4的倍数s中只含有'Q','W','E','R'四种字符
测试链接
思路
滑动窗口的关键：找到范围和答案指标之间的单调性关系
窗口表示可替换的子串，窗口越长，越容易使整个字符串变成「平衡字符串」
范围右指针向右阔：达不到平衡字符串，继续加可变范围
范围左指针向右阔：以
l开始的答案收集了，继续收集下一个位置
滑动过程：滑动窗口可以用简单变量或者结构来维护信息
cnts窗口之外的各个字符数量，用于判断如果当前窗口范围可变，能不能达成要求；
求解大流程：求子数组在每个位置开头或结尾情况下的答案
求在每个位置开头情况下的答案
答案
func balancedString(s string) int {
n := len(s)
// 窗口之外的各个字符数量
cnts := [4]int{}
for i := 0; i < n; i++ {
cnts[getIdx(s[i])]++
}
// 每种字符应该出现的次数
required := n / 4
// 最多把把整个字符串都改了
ans := n
// 窗口：[r, l)
r := 0
for l := 0; l < n; l++ {
for !ok(cnts, r-l, required) && r < n {
cnts[getIdx(s[r])]--
r++
}
if ok(cnts, r-l, required) {
ans = min(ans, r-l)
}
cnts[getIdx(s[l])]++
}
return ans
}
// cnts: l...r 范围上的字符不算！在自由变化的窗口之外，每一种字符的词频统计
// size: 自由变化窗口的长度
// required: 每一种字符都要达到的数量
// 返回值: 能不能做到
func ok(cnts [4]int, size, required int) bool {
for _, cnt := range cnts {
if cnt > required { // 自由变化的窗口之外的字符多了，肯定达不到
return false
}
size -= required - cnt
}
// 需要添加的字符数量等于自由变化字符数量
return size == 0
}
func getIdx(char byte) int {
switch char {
case 'Q':
return 0
case 'W':
return 1
case 'E':
return 2
case 'R':
return 3
}
panic("Illegal input")
}复杂度
- 时间复杂度：，
l、r都不回退 - 空间复杂度：
题目6.K 个不同整数的子数组
题目描述
给定一个正整数数组 nums 和一个整数 k，返回 nums 中 「好子数组」 的数目。
如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为「好子数组 」。
- 例如，
[1,2,3,1,2]中有3个不同的整数：1，2，以及3。
子数组 是数组的 连续 部分。
提示：
1 <= nums.length <= 2 * 10^41 <= nums[i], k <= nums.length
测试链接
思路
直接求子数组数字种类等于 k 的话，窗口范围大小和数字种类等于 k 没有单调性，将题目转换成求子数组数字种类小于等于 k
子数组数字种类等于 k = 子数组数字种类小于等于 k - 子数组数字种类小于等于 k-1
滑动窗口的关键：找到范围和答案指标之间的单调性关系
窗口越短，子数组数字种类越容易小于等于
k范围右指针向右阔：还小于等于，继续加字符
范围左指针向右阔：不小于等于了，减字符，直到继续小于等于
滑动过程：滑动窗口可以用简单变量或者结构来维护信息
cnts窗口内的各个字符数量；
cnt窗口内数字种类
求解大流程：求子数组在每个位置开头或结尾情况下的答案
求在每个位置结尾情况下的答案
答案
const (
MAXN = 20001
)
var (
cnts = [MAXN]int{}
)
func subarraysWithKDistinct(nums []int, k int) int {
return numsOfMostKinds(nums, k) - numsOfMostKinds(nums, k-1)
}
// nums 中有多少子数组，数字种类不超过 k
// nums 的长度是 n，nums 里的数值 1~n 之间
func numsOfMostKinds(nums []int, k int) int {
n := len(nums)
ans := 0
l := 0
// 当前窗口中的数字种类
cnt := 0
for r := 0; r < n; r++ {
if cnts[nums[r]] == 0 {
cnt++
}
cnts[nums[r]]++
for cnt > k {
cnts[nums[l]]--
if cnts[nums[l]] == 0 {
cnt--
}
l++
}
// 以 r 结尾的子数组，数字种类不超过 k 的子数组个数
ans += r - l + 1
}
clear(n)
return ans
}
func clear(n int) {
for i := 0; i <= n; i++ {
cnts[i] = 0
}
}复杂度
- 时间复杂度：，
l、r都不回退 - 空间复杂度：，
cnts：数组数值在 之间
题目7.至少有 K 个重复字符的最长子串
题目描述
给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k。返回这一子串的长度。
如果不存在这样的子字符串，则返回 0。
提示：
1 <= s.length <= 10^4s仅由小写英文字母组成1 <= k <= 10^5
测试链接
思路
将问题转换为：求子串出现 1 个字符，这个字符出现次数都不少于 k 的最长子串、求子串出现 2 个字符，这些字符出现次数都不少于 k 的最长子串、…、求子串出现 26 个字符，这些字符出现次数都不少于 k 的最长子串
滑动窗口的关键：找到范围和答案指标之间的单调性关系
窗口越长，子数组数字种类和个数越多
滑动过程：滑动窗口可以用简单变量或者结构来维护信息
cnts窗口内的各个字符数量；
collect窗口内数字种类；
satisfy窗口中达标的种类数(次数 >=k)
求解大流程：求子数组在每个位置开头或结尾情况下的答案
求在每个位置结尾情况下的答案
字符种类有限个时可以使用滑动窗口的解法，当字符种类太多时就不适用了，需要用动态规划来解决，但不是本节的重点
答案
func longestSubstring(s string, k int) int {
n := len(s)
cnts := [26]int{}
ans := 0
// 每次要求子串必须含有 require 种字符，每种字符都必须 >=k 次，这样的最长子串是多长
for require := 1; require <= 26; require++ {
l := 0
// 窗口中一共收集到的种类数
collect := 0
// 窗口中达标的种类数(次数 >=k)
satisfy := 0
for r := 0; r < n; r++ {
cnts[s[r] - 'a']++
if cnts[s[r] - 'a'] == 1 {
collect++
}
if cnts[s[r] - 'a'] == k {
satisfy++
}
for collect > require { // 种类超了，往出吐数字
if cnts[s[l] - 'a'] == 1 {
collect--
}
if cnts[s[l] - 'a'] == k {
satisfy--
}
cnts[s[l] - 'a']--
l++
}
if satisfy == require {
// l...r: 子串以 r 位置的字符结尾，且种类数不超的最大长度
ans = max(ans, r-l+1)
}
}
for i := range cnts {
cnts[i] = 0
}
}
return ans
}复杂度
- 时间复杂度：，
l、r都不回退，26 次循环 - 空间复杂度：，26 长度的数组
备注
滑动窗口维持最大值或者最小值的更新结构，在【必备】课程【单调队列】视频里讲述