【算法刷题笔记day one】滑动窗口（定长基础版）

前言

hello大家好呀 好久不见，上次更新是去年12月份的事情了。这段时间好好沉淀了一下，打了几场比赛，论文也写了一些，也收集了不少信息，对未来方向也有了不一样的计划。

这个算法系列可以说是接着我之前的数据结构系列的升级版，我不会再出数据结构的单独的文章，这些内容会放在算法讲解部分一起出。另外可能还会出一些我在做研究的过程中，解决问题的一些教程。（机器学习部分后面有时间再说吧，毕竟我也不是科普博主）这个系列会持续到我把力扣上题单刷完为止。

正如题目所言，我这里写的都是我的学习笔记，是个人的一些思考，主要是方便后面我回来复习，也希望可以对大家有些启发。我的博客里面所有的题目是我提炼出来比较有代表性的，在力扣上都可以找的到，我也会放链接。（代码大部分是我手搓的，可能不是那么优雅，如果有这方面需求的话，大家可以去题解找找看其他大佬的代码）

好了，闲话就说这么多，让我们开始学习吧

一、基础滑窗

1、基础思路

定长滑窗套路
可以总结成三步：入-更新值-出。

入：下标为 i 的元素进入窗口，更新相关统计量。如果 i<k−1 则重复第一步。
更新：更新答案。一般是更新最大值/最小值。
出：下标为 i−k+1 的元素离开窗口，更新相关统计量。

以上三步适用于所有定长滑窗题目。

图示（来源：灵神）

2、例题1 — 1456.定长子串中元音的最大数目

给你字符串 s 和整数 k 。

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的 元音字母 为（a, e, i, o, u）。

示例 1：

输入：s = "abciiidef", k = 3
输出：3
解释：子字符串 "iii" 包含 3 个元音字母。

示例 2：

输入：s = "aeiou", k = 2
输出：2
解释：任意长度为 2 的子字符串都包含 2 个元音字母。

示例 3：

输入：s = "leetcode", k = 3
输出：2
解释："lee"、"eet" 和 "ode" 都包含 2 个元音字母。

示例 4：

输入：s = "rhythms", k = 4
输出：0
解释：字符串 s 中不含任何元音字母。

示例 5：

输入：s = "tryhard", k = 4
输出：1

提示：

• 1 <= s.length <= 10^5
• s 由小写英文字母组成
• 1 <= k <= s.length

class Solution:def maxVowels(self, s: str, k: int) -> int:l = ans = res = 0 #l为窗口左边界，ans为动态变化的窗口内题目要求的值，res记录最大值for i, c in enumerate(s):if i <= k - 1: #个人习惯加上‘=’，那么下面就要多个max判断                   if c in 'aeiou': #否则len（s） == k - 1时，res值会错误更新ans += 1res = max(ans, res)else:if s[l] in 'aeiou': ans -= 1if c in 'aeiou':ans += 1l += 1res = max(res, ans) #动态更新窗口和值return res

#举例
示例 1，s=abciiidef, k=3。

从左到右遍历 s。
首先统计前 k−1=2 个字母的元音个数，这有 1 个。
s[2]=c 进入窗口，此时找到了第一个长为 k 的子串 abc，现在元音个数有 1 个，更新答案最大值。然后 s[0]=a 离开窗口，现在元音个数有 0 个。
s[3]=i 进入窗口，此时找到了第二个长为 k 的子串 bci，现在元音个数有 1 个，更新答案最大值。然后 s[1]=b 离开窗口，现在元音个数有 1 个。
s[4]=i 进入窗口，此时找到了第三个长为 k 的子串 cii，现在元音个数有 2 个，更新答案最大值。然后 s[2]=c 离开窗口，现在元音个数有 2 个。
s[5]=i 进入窗口，此时找到了第四个长为 k 的子串 iii，现在元音个数有 3 个，更新答案最大值。然后 s[3]=i 离开窗口，现在元音个数有 2 个。
s[6]=d 进入窗口，此时找到了第五个长为 k 的子串 iid，现在元音个数有 2 个，更新答案最大值。然后 s[4]=i 离开窗口，现在元音个数有 1 个。
s[7]=e 进入窗口，此时找到了第六个长为 k 的子串 ide，现在元音个数有 2 个，更新答案最大值。然后 s[5]=i 离开窗口，现在元音个数有 1 个。
s[8]=f 进入窗口，此时找到了第七个长为 k 的子串 def，现在元音个数有 1 个，更新答案最大值。遍历结束。

3、例题2 — 2090.半径为k的子数组平均值

给你一个下标从 0 开始的数组 nums ，数组中有 n 个整数，另给你一个整数 k 。

半径为 k 的子数组平均值 是指：nums 中一个以下标 i 为 中心 且 半径 为 k 的子数组中所有元素的平均值，即下标在 i - k 和 i + k 范围（含 i - k 和 i + k）内所有元素的平均值。如果在下标 i 前或后不足 k 个元素，那么 半径为 k 的子数组平均值 是 -1 。

构建并返回一个长度为 n 的数组 avgs ，其中 avgs[i] 是以下标 i 为中心的子数组的 半径为 k 的子数组平均值 。

x 个元素的 平均值 是 x 个元素相加之和除以 x ，此时使用截断式 整数除法 ，即需要去掉结果的小数部分。

• 例如，四个元素 2、3、1 和 5 的平均值是 (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75，截断后得到 2 。

示例 1：

输入：nums = [7,4,3,9,1,8,5,2,6], k = 3
输出：[-1,-1,-1,5,4,4,-1,-1,-1]
解释：
- avg[0]、avg[1] 和 avg[2] 是 -1 ，因为在这几个下标前的元素数量都不足 k 个。
- 中心为下标 3 且半径为 3 的子数组的元素总和是：7 + 4 + 3 + 9 + 1 + 8 + 5 = 37 。使用截断式 整数除法，avg[3] = 37 / 7 = 5 。
- 中心为下标 4 的子数组，avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4 。
- 中心为下标 5 的子数组，avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4 。
- avg[6]、avg[7] 和 avg[8] 是 -1 ，因为在这几个下标后的元素数量都不足 k 个。

示例 2：

输入：nums = [100000], k = 0
输出：[100000]
解释：
- 中心为下标 0 且半径 0 的子数组的元素总和是：100000 。avg[0] = 100000 / 1 = 100000 。

示例 3：

输入：nums = [8], k = 100000
输出：[-1]
解释：
- avg[0] 是 -1 ，因为在下标 0 前后的元素数量均不足 k 。

提示：

• n == nums.length
• 1 <= n <= 105
• 0 <= nums[i], k <= 105

class Solution:def getAverages(self, nums: List[int], k: int) -> List[int]:avgs = [-1] * len(nums) #初始化数组ans = l = 0 #左边界和窗口数组和if k == 0:return numselif k > len(nums) // 2: #示例的特殊情况处理return avgselse: #注意不要重复returnfor i, c in enumerate(nums):if i < 2 * k:ans += c #把半径想象成两倍长的窗口else:ans += cavgs[(i + l) // 2] = ans // (k * 2 + 1) #中心点是向前移动，要用加ans -= nums[l]                          #要时刻记住窗口长度是2k+1l += 1return avgs

#思路：

本题相当于一个长为 2k+1 的滑动窗口。

入：下标为 i 的元素进入窗口，窗口元素和 s 增加 nums[i]。如果 i<2k 则重复第一步。
更新：本题只需记录答案，即 
                                ​
其中 i−k 是因为 i 对应的是子数组右端点，而记录答案的位置是子数组的正中间。
出：下标为 i−2k 的元素离开窗口，窗口元素和 s 减少 nums[i−2k]。

                                        
以上三步适用于所有定长滑窗题目。

4、例题3 — 2841.几乎唯一子数组的最大和

给你一个整数数组 nums 和两个正整数 m 和 k 。

请你返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0 。

如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。

子数组指的是一个数组中一段连续 非空 的元素序列。

示例 1：

输入：nums = [2,6,7,3,1,7], m = 3, k = 4
输出：18
解释：总共有 3 个长度为 k = 4 的几乎唯一子数组。分别为 [2, 6, 7, 3] ，[6, 7, 3, 1] 和 [7, 3, 1, 7] 。这些子数组中，和最大的是 [2, 6, 7, 3] ，和为 18 。

示例 2：

输入：nums = [5,9,9,2,4,5,4], m = 1, k = 3
输出：23
解释：总共有 5 个长度为 k = 3 的几乎唯一子数组。分别为 [5, 9, 9] ，[9, 9, 2] ，[9, 2, 4] ，[2, 4, 5] 和 [4, 5, 4] 。这些子数组中，和最大的是 [5, 9, 9] ，和为 23 。

示例 3：

输入：nums = [1,2,1,2,1,2,1], m = 3, k = 3
输出：0
解释：输入数组中不存在长度为 k = 3 的子数组含有至少  m = 3 个互不相同元素的子数组。所以不存在几乎唯一子数组，最大和为 0 。

提示：

• 1 <= nums.length <= 2 * 104
• 1 <= m <= k <= nums.length
• 1 <= nums[i] <= 109

class Solution:def maxSum(self, nums: List[int], m: int, k: int) -> int:ans = s = 0 #答案与和cnt = defaultdict(int) #特殊字典，在返回未存在的键时会返回括号内的类型for i, x in enumerate(nums):# 1. 进入窗口s += xcnt[x] += 1left = i - k + 1if left < 0:  # 窗口大小不足 kcontinue# 2. 更新答案if len(cnt) >= m: #通过字典键的种类来判断有几种字符ans = max(ans, s)# 3. 离开窗口out = nums[left]s -= outcnt[out] -= 1if cnt[out] == 0:del cnt[out] #动态更新字典return ans#没法用集合，因为如果有两个同样的数，虽然此时计数正确，但是只要有一个数被删去，就会少记一个数

5、例题4 — 1423.可获得的最大点数（算法逻辑）

几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。

每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。

你的点数就是你拿到手中的所有卡牌的点数之和。

给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

示例 1：

输入：cardPoints = [1,2,3,4,5,6,1], k = 3
输出：12
解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。

示例 2：

输入：cardPoints = [2,2,2], k = 2
输出：4
解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。

示例 3：

输入：cardPoints = [9,7,7,9,7,7,9], k = 7
输出：55
解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。

示例 4：

输入：cardPoints = [1,1000,1], k = 1
输出：1
解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。 

示例 5：

输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
输出：202

提示：

• 1 <= cardPoints.length <= 10^5
• 1 <= cardPoints[i] <= 10^4
• 1 <= k <= cardPoints.length

class Solution:def maxScore(self, cardPoints: List[int], k: int) -> int:n = len(cardPoints)m = n - k #最后会省的数组的长度，也就是我们窗口的长度ans = res = sum(cardPoints[:m]) #初始化for i in range(m, n):ans += cardPoints[i] - cardPoints[i - m]res = min(ans, res) #要得到拿走的最大点数，就是要留下最小的点数return sum(cardPoints) - res #注意求得的是留下的点数

#逆向思维
拿走 k 张，剩下 n−k 张。这里 n 是 cardPoints 的长度。

由于拿走的点数和 + 剩下的点数和 = 所有点数和 = 常数，所以为了最大化拿走的点数和，应当最小化剩下的点数和。

由于只能从开头或末尾拿牌，所以最后剩下的牌必然是连续的。

至此，问题变成：

计算长为 n−k 的连续子数组和的最小值。
这可以用滑动窗口解决。

二、进阶滑窗

1、基础思路

进阶版的滑动窗口题目需要多一层思考，无法一眼就看出这是一道滑窗的题目，需要将题目要求进行转化。这种题目一般滑窗是可以解决，但是在此基础上，还需要其他的一些方法来辅助。解决办法就是多多做，熟能生巧。

2、例题5 — 3439.重新安排会议得到的最多空余时间 （1）

给你一个整数 eventTime 表示一个活动的总时长，这个活动开始于 t = 0 ，结束于 t = eventTime 。

同时给你两个长度为 n 的整数数组 startTime 和 endTime 。它们表示这次活动中 n 个时间 没有重叠 的会议，其中第 i 个会议的时间为 [startTime[i], endTime[i]] 。

你可以重新安排 至多 k 个会议，安排的规则是将会议时间平移，且保持原来的 会议时长 ，你的目的是移动会议后 最大化 相邻两个会议之间的 最长 连续空余时间。

移动前后所有会议之间的 相对 顺序需要保持不变，而且会议时间也需要保持互不重叠。

请你返回重新安排会议以后，可以得到的 最大 空余时间。

注意，会议 不能 安排到整个活动的时间以外。

示例 1：

输入：eventTime = 5, k = 1, startTime = [1,3], endTime = [2,5]

输出：2

解释：

将 [1, 2] 的会议安排到 [2, 3] ，得到空余时间 [0, 2] 。

示例 2：

输入：eventTime = 10, k = 1, startTime = [0,2,9], endTime = [1,4,10]

输出：6

解释：

将 [2, 4] 的会议安排到 [1, 3] ，得到空余时间 [3, 9] 。

示例 3：

输入：eventTime = 5, k = 2, startTime = [0,1,2,3,4], endTime = [1,2,3,4,5]

输出：0

解释：

活动中的所有时间都被会议安排满了。

提示：

• 1 <= eventTime <= 109
• n == startTime.length == endTime.length
• 2 <= n <= 105
• 1 <= k <= n
• 0 <= startTime[i] < endTime[i] <= eventTime
• endTime[i] <= startTime[i + 1] 其中 i 在范围 [0, n - 2] 之间。

class Solution:def maxFreeTime(self, eventTime: int, k: int, startTime: List[int], endTime: List[int]) -> int:avg = [] #记录空闲时间的数组，也是拿来滑的数组，这一步是关键思路avg.append(startTime[0]) #无论是否从0开始，都要把这个差值记录for i in range(1, len(startTime)): #初始化，是否为0都要记录temp = startTime[i] - endTime[i - 1] #下一个开始减上一个结束为等待时间avg.append(temp)if i == len(startTime) - 1:avg.append(eventTime - endTime[i]) #同上if k == 0:return max(avg) #k为0则不动elif len(avg) == 0:return 0 #若全为数组0说明排满了else:        #转化为滑窗求解最大值t = k + 1s = ans = l = 0for i, x in enumerate(avg):if i < t - 1:s += xcontinues += xans = max(ans, s)s -= avg[l]l += 1return ans

#注意：数组一定要把所有差值包括开头结尾，包括所有为0 的差值，如果不计，分别出现数组不够长、将两个会议视为一个的错误

#思路

看示例 1，把会议区间 [1,2] 移动到 [0,1] 或者 [2,3]，会产生空余时间段 [1,3] 或者 [0,2]，相当于把两个相邻的长为 1 空余时间段 [0,1] 和 [2,3] 合并成一个更大的长为 1+1=2 的空余时间段。

题目要求会议之间的相对顺序需要保持不变，这意味着我们只能合并相邻的空余时间段，所以重新安排至多 k 个会议等价于如下问题：

给你 n+1 个空余时间段，合并其中 k+1 个连续的空余时间段，得到的最大长度是多少？
这可以用定长滑动窗口解决

3、例题6 — 2134.最小交换次数来组合所有的1（2）

交换 定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。

环形 数组是一个数组，可以认为 第一个 元素和 最后一个 元素 相邻 。

给你一个 二进制环形 数组 nums ，返回在 任意位置 将数组中的所有 1 聚集在一起需要的最少交换次数。

示例 1：

输入：nums = [0,1,0,1,1,0,0]
输出：1
解释：这里列出一些能够将所有 1 聚集在一起的方案：
[0,0,1,1,1,0,0] 交换 1 次。
[0,1,1,1,0,0,0] 交换 1 次。
[1,1,0,0,0,0,1] 交换 2 次（利用数组的环形特性）。
无法在交换 0 次的情况下将数组中的所有 1 聚集在一起。
因此，需要的最少交换次数为 1 。

示例 2：

输入：nums = [0,1,1,1,0,0,1,1,0]
输出：2
解释：这里列出一些能够将所有 1 聚集在一起的方案：
[1,1,1,0,0,0,0,1,1] 交换 2 次（利用数组的环形特性）。
[1,1,1,1,1,0,0,0,0] 交换 2 次。
无法在交换 0 次或 1 次的情况下将数组中的所有 1 聚集在一起。
因此，需要的最少交换次数为 2 。

示例 3：

输入：nums = [1,1,0,0,1]
输出：0
解释：得益于数组的环形特性，所有的 1 已经聚集在一起。
因此，需要的最少交换次数为 0 。

提示：

• 1 <= nums.length <= 105
• nums[i] 为 0 或者 1

class Solution:def minSwaps(self, nums: List[int]) -> int:n = len(nums) k = sum(nums) #通过数组的和来判断有几个1s = sum(nums[0:k]) #初始化动态和，这是第一个滑窗res = k-s #初始化需要交换的次数for i in range(1,n):s+=nums[(i+k-1)%n]-nums[i-1] #因为是循环数组，需要遍历完一整圈res = min(res,k-s) #求最小交换次数return res
#通过滑窗的值与数组的和来判断需要这个滑窗交换几次

#思路

解题方法

将题目转化，要将更多的1聚在一起，可以转化为在长为counter的滑动窗口内找更多的1，counter则是nums中所有1的数量 对于环的处理，对nums数组长度取余数（模处理）就可以处理环的问题

然后就成了标准滑动窗口问题了

4、例题7 — 2653.滑动子数组的美丽值（时间限制-计数排序）

给你一个长度为 n 的整数数组 nums ，请你求出每个长度为 k 的子数组的 美丽值 。

一个子数组的 美丽值 定义为：如果子数组中第 x 小整数 是 负数 ，那么美丽值为第 x 小的数，否则美丽值为 0 。

请你返回一个包含 n - k + 1 个整数的数组，依次 表示数组中从第一个下标开始，每个长度为 k 的子数组的 美丽值 。

• 子数组指的是数组中一段连续 非空 的元素序列。

示例 1：

输入：nums = [1,-1,-3,-2,3], k = 3, x = 2
输出：[-1,-2,-2]
解释：总共有 3 个 k = 3 的子数组。
第一个子数组是 [1, -1, -3] ，第二小的数是负数 -1 。
第二个子数组是 [-1, -3, -2] ，第二小的数是负数 -2 。
第三个子数组是 [-3, -2, 3] ，第二小的数是负数 -2 。

示例 2：

输入：nums = [-1,-2,-3,-4,-5], k = 2, x = 2
输出：[-1,-2,-3,-4]
解释：总共有 4 个 k = 2 的子数组。
[-1, -2] 中第二小的数是负数 -1 。
[-2, -3] 中第二小的数是负数 -2 。
[-3, -4] 中第二小的数是负数 -3 。
[-4, -5] 中第二小的数是负数 -4 。

示例 3：

输入：nums = [-3,1,2,-3,0,-3], k = 2, x = 1
输出：[-3,0,-3,-3,-3]
解释：总共有 5 个 k = 2 的子数组。
[-3, 1] 中最小的数是负数 -3 。
[1, 2] 中最小的数不是负数，所以美丽值为 0 。
[2, -3] 中最小的数是负数 -3 。
[-3, 0] 中最小的数是负数 -3 。
[0, -3] 中最小的数是负数 -3 。

错误代码（完全暴力，可以解题但是会超时，差14个测试点）

class Solution:def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:avg = []ans = []n = len(nums)for i in range(n - k + 1):ans = nums[i : i + k]ans.sort()if ans[x - 1] < 0:avg.append(ans[x - 1])else:avg.append(0)return avg

正解：滑窗+计数排序+枚举

class Solution:def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:cnt = [0] * 101 #计数排序，如果是负数数组索引就会从后往前遍历，即从小到大#索引的值就是这个数出现的次数，拿这个值去扣xfor num in nums[:k - 1]:  # 先往窗口内添加 k-1 个数，初始化cnt[num] += 1ans = [0] * (len(nums) - k + 1)for i, (in_, out) in enumerate(zip(nums[k - 1:], nums)):#in就是要进入的数，out就是要出去的数，先进再出，经典滑窗cnt[in_] += 1  #进入窗口（保证窗口有恰好 k 个数）left = xfor j in range(-50, 0):  # 暴力枚举负数范围 [-50,-1]left -= cnt[j]if left <= 0:  # 找到美丽值，没找到就直接是0ans[i] = jbreakcnt[out] -= 1  # 离开窗口return ans

#思路

由于值域很小，所以借鉴计数排序，用一个 cnt 数组维护窗口内每个数的出现次数。然后遍历 cnt 去求第 x 小的数。

什么是第 x 小的数？

设它是 num，那么 <num 的数有 <x 个，≤num 的数有 ≥x 个，就说明 num 是第 x 小的数。

比如 [−1,−1,−1] 中，第 1,2,3 小的数都是 −1

三、其他滑窗

1、基础思路

在这一部分，滑窗更多的作为工具，整个题目主要运用的其他的思想来找到突破口。

2、例题8 — 1984.学生分数的最小差值

给你一个 下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。

从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。

返回可能的 最小差值 。

示例 1：

输入：nums = [90], k = 1
输出：0
解释：选出 1 名学生的分数，仅有 1 种方法：
- [90] 最高分和最低分之间的差值是 90 - 90 = 0
可能的最小差值是 0

示例 2：

输入：nums = [9,4,1,7], k = 2
输出：2
解释：选出 2 名学生的分数，有 6 种方法：
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 = 5
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 = 8
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 = 2
- [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 = 6
可能的最小差值是 2

提示：

• 1 <= k <= nums.length <= 1000
• 0 <= nums[i] <= 105

class Solution:def minimumDifference(self, nums: List[int], k: int) -> int:n = len(nums)nums.sort() #排序成新数组ans = inf   #初始化ans值，这里应该是从from math import inf 导入for i in range(n - k + 1): #按照k长的滑窗遍历，寻找最小值ans = min(ans, nums[i + k - 1] - nums[i])return ans

#思路（贪心的正确性）

• 在一个已排序的数组中（转化的过程），想要选出 k 个数使得「最大值–最小值」最小，最优解一定出现在某个长度为 k 的连续子区间。（滑窗）

• 因此，排序后只需检查所有长度为 k 的连续子区间即可，不必穷举组合。

• 注意不可以直接用贪心的思路去找两个最大值，如例2，nums的k个最大值差值不一定最小

3、例题9 — 2269.找到一个数字的k美丽值

一个整数 num 的 k 美丽值定义为 num 中符合以下条件的 子字符串 数目：

• 子字符串长度为 k 。
• 子字符串能整除 num 。

给你整数 num 和 k ，请你返回 num 的 k 美丽值。

注意：

• 允许有 前缀 0 。
• 0 不能整除任何值。

一个 子字符串 是一个字符串里的连续一段字符序列。

示例 1：

输入：num = 240, k = 2
输出：2
解释：以下是 num 里长度为 k 的子字符串：
- "240" 中的 "24" ：24 能整除 240 。
- "240" 中的 "40" ：40 能整除 240 。
所以，k 美丽值为 2 。

示例 2：

输入：num = 430043, k = 2
输出：2
解释：以下是 num 里长度为 k 的子字符串：
- "430043" 中的 "43" ：43 能整除 430043 。
- "430043" 中的 "30" ：30 不能整除 430043 。
- "430043" 中的 "00" ：0 不能整除 430043 。
- "430043" 中的 "04" ：4 不能整除 430043 。
- "430043" 中的 "43" ：43 能整除 430043 。
所以，k 美丽值为 2 。

提示：

• 1 <= num <= 109
• 1 <= k <= num.length （将 num 视为字符串）

class Solution:def divisorSubstrings(self, num: int, k: int) -> int:s = str(num)n = len(s)ans = 0# 枚举所有长度为 k 的连续子串for i in range(n - k + 1):sub = s[i : i + k]       # 取出 s[i]…s[i+k-1]if int(sub) != 0 and num % int(sub) == 0:ans += 1return ans

#思路

• s = str(num)：把原整数转成字符串，方便切片。

• for i in range(n - k + 1)：一共能切出 n-k+1 个长度为 k 的子串。

• sub = s[i:i+k]：这是最直接、最不易出错的滑窗方式。

• int(sub) != 0：防止除零。

• 时间复杂度 O(n·k)，空间复杂度 O(n)。

四、尾声

定长滑窗的笔记就到这了。总结一下，定长滑窗整体套路还是非常明显，题目都可以转化成求n个确定的长度区间内的一种值。写法都是转化思想加上滑窗计数，属于入门级别的算法。

接下来是不定长滑窗，由于我是分天边刷边总结，把提单刷完才会发，所以一篇笔记可能会要好几天，大家敬请期待。

本期文章就到这里，有问题欢迎在评论区讨论，我看到会马上回复。拜拜~~