【滑动窗口算法】——定长滑动窗口——Python（附题）

一.定长滑动窗口是什么及其使用场景

定长滑动窗口算法的核心思想是使用两个指针，通常称为“左指针”和“右指针”。窗口的大小是固定的，右指针用于扩展窗口，直到达到指定大小，而左指针则在窗口移动时逐步向右滑动。这样可以高效地更新窗口内的计算结果，避免重复计算。

二.刷题 + 题解（在代码中）

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 = 0 ; r = 1 # 建立两个指针if s[l] in "aeiou":ans = 1else:ans = 0e = float("-inf")while r <= len(s):                if s[r] in "aeiou":ans += 1        r += 1if r - l > k: # 当两个指针大于k（窗口长度）那么左指针将要向右滑动if s[l] in "aeiou":ans -= 1l += 1 e = max(ans,e)            if r == len(s):breakreturn e

643. 子数组最大平均数 I

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

任何误差小于 10-5 的答案都将被视为正确答案。

示例 1：

输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

示例 2：

输入：nums = [5], k = 1
输出：5.00000

提示：

• n == nums.length
• 1 <= k <= n <= 10**5
• -10**4 <= nums[i] <= 10**4

# 这道题主要考察的区间和，主要怎么思考呢
# 1.先算出这个从0开始的窗口和。
# 2.移动指针，当移动右指针时，这个和就要加上右指针指向的值，同时左指针移动时，这个和就要减 去左指针移动前的值。
# 3.通过以上方法动态维护窗口内的和。
# 4.求区间和也可以用前缀和来求但是时间复杂度是o（2n）的，好处是以后无需再遍历。
class Solution:def findMaxAverage(self, nums: List[int], k: int) -> float:average = sum(nums[0:k]) / ksum1 = average * ki = 0while k < len(nums):sum1 -= nums[i]k += 1i += 1       sum1 += nums[k - 1]average = max(sum1 / (k - i), average)         return average

 1343. 大小为 K 且平均值大于等于阈值的子数组数目

给你一个整数数组 arr 和两个整数 k 和 threshold 。

请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。

示例 1：

输入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
输出：3
解释：子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分别为 4，5 和 6 。其他长度为 3 的子数组的平均值都小于 4 （threshold 的值)。

示例 2：

输入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
输出：6
解释：前 6 个长度为 3 的子数组平均值都大于 5 。注意平均值不是整数。

提示：

• 1 <= arr.length <= 10**5
• 1 <= arr[i] <= 10**4
• 1 <= k <= arr.length
• 0 <= threshold <= 10**4

class Solution:def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:ans = 0target = k * thresholdpre = 0n = len(arr)for i in range(n): # 右指针为ipre += arr[i]if i >= k:pre -= arr[i - k] # 左指针为i - kif i >= k - 1 and pre >= target:ans += 1return ans

 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 <= 10**5
• 0 <= nums[i], k <= 10**5

# 以下使用前缀和做的，也可以用“右指针加入左指针相减（上文提到过）”来维护和
class Solution:def getAverages(self, nums: List[int], k: int) -> List[int]:if k == 0:return numsn = len(nums)l = []o = list(accumulate(nums))o = [0] + ofor i in range(n):if i - k < 0 or i + k > n - 1:l.append(-1)else:l.append((o[i + k + 1] - o[i - k]) // (2 * k + 1))return l

2379. 得到 K 个黑块的最少涂色次数

给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 'W' 要么是 'B' ，表示第 i 块的颜色。字符 'W' 和 'B' 分别表示白色和黑色。

给你一个整数 k ，表示想要 连续 黑色块的数目。

每一次操作中，你可以选择一个白色块将它 涂成 黑色块。

请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数。

示例 1：

输入：blocks = "WBBWWBBWBW", k = 7
输出：3
解释：
一种得到 7 个连续黑色块的方法是把第 0 ，3 和 4 个块涂成黑色。
得到 blocks = "BBBBBBBWBW" 。
可以证明无法用少于 3 次操作得到 7 个连续的黑块。
所以我们返回 3 。

示例 2：

输入：blocks = "WBWBBBW", k = 2
输出：0
解释：
不需要任何操作，因为已经有 2 个连续的黑块。
所以我们返回 0 。

提示：

• n == blocks.length
• 1 <= n <= 100
• blocks[i] 要么是 'W' ，要么是 'B' 。
• 1 <= k <= n

'''
目的：求每个窗口中B的个数。关于求窗口里的个数而不是求和，最好的统计方法肯定是字典，出去了就将键对应的值减一，进去就加一，每次操作维护B出现的最少次数
'''
class Solution:def minimumRecolors(self, blocks: str, k: int) -> int:dict1 = Counter(blocks[:k])ans = float("inf")n = len(blocks)if n == k:return blocks.count("W")for i in range(k,n):ans = min(ans,dict1["W"])dict1[blocks[i - k]] -= 1dict1[blocks[i]] += 1return min(ans,dict1["W"])

 1652. 拆炸弹

你有一个炸弹需要拆除，时间紧迫！你的情报员会给你一个长度为 n 的 循环 数组 code 以及一个密钥 k 。

为了获得正确的密码，你需要替换掉每一个数字。所有数字会 同时 被替换。

• 如果 k > 0 ，将第 i 个数字用 接下来 k 个数字之和替换。
• 如果 k < 0 ，将第 i 个数字用 之前 k 个数字之和替换。
• 如果 k == 0 ，将第 i 个数字用 0 替换。

由于 code 是循环的， code[n-1] 下一个元素是 code[0] ，且 code[0] 前一个元素是 code[n-1] 。

给你 循环 数组 code 和整数密钥 k ，请你返回解密后的结果来拆除炸弹！

示例 1：

输入：code = [5,7,1,4], k = 3
输出：[12,10,16,13]
解释：每个数字都被接下来 3 个数字之和替换。解密后的密码为 [7+1+4, 1+4+5, 4+5+7, 5+7+1]。注意到数组是循环连接的。

示例 2：

输入：code = [1,2,3,4], k = 0
输出：[0,0,0,0]
解释：当 k 为 0 时，所有数字都被 0 替换。

示例 3：

输入：code = [2,4,9,3], k = -2
输出：[12,5,6,13]
解释：解密后的密码为 [3+9, 2+3, 4+2, 9+4] 。注意到数组是循环连接的。如果 k 是负数，那么和为 之前 的数字。

提示：

• n == code.length
• 1 <= n <= 100
• 1 <= code[i] <= 100
• -(n - 1) <= k <= n - 1

# 难点是首尾是相连，如何实现呢，很简单，将右窗口和左窗口的指针（这里设为P）每次索引时对列表长度取余即可。
class Solution:def decrypt(self, code: List[int], k: int) -> List[int]:n = len(code)ans = [0] * nif k == 0:return anss = list(accumulate(code + code, initial = 0))for i in range(n):if k > 0:ans[i] = s[i + k + 1] - s[i + 1]else:ans[i] = s[i + n] - s[i + k + n]return ans

 1052. 爱生气的书店老板

有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。

在某些分钟内，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。

当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。

书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。

请你返回 这一天营业下来，最多有多少客户能够感到满意 。
 

示例 1：

输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
输出：16
解释：书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

示例 2：

输入：customers = [1], grumpy = [0], minutes = 1
输出：1

提示：

• n == customers.length == grumpy.length
• 1 <= minutes <= n <= 2 * 10**4
• 0 <= customers[i] <= 1000
• grumpy[i] == 0 or 1

'''
目的：找在以min大小的窗口什么时候能把损失降到最低，就是维护一个在窗内生气时候的客人总数，并且维护这个最大值
'''
class Solution:def maxSatisfied(self, customers: List[int], grumpy: List[int], k: int) -> int:n = len(customers)suf = [0] * (n + 1)for i in range(n - 1, -1, -1): suf[i] = suf[i + 1] + customers[i] * (1 - grumpy[i])pre = 0cur = sum(customers[:k])ans = cur + pre + suf[k]for i in range(k, n):pre += (1 - grumpy[i - k]) * customers[i - k]cur += customers[i] - customers[i - k]ans = max(ans, pre + cur + suf[i + 1])return ans

 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 * 10**4
• 1 <= m <= k <= nums.length
• 1 <= nums[i] <= 10**9

'''
m个互不相同的元素是难点，不同，可以想到集合去重然后算出元素个数也就是长度，但是set需要n，len也需要n，时间复杂度就上来了，有个方法是统计，用字典。当值为零时将这个键删去，这都是0（1）的，然用len来算出不用的个数即可。
'''
class Solution:def maxSum(self, nums: List[int], m: int, k: int) -> int:ans = 0s = sum(nums[:k - 1])cnt = Counter(nums[:k - 1])for out , in_ in zip(nums,nums[k - 1:]):s += in_cnt[in_] += 1if len(cnt) >= m:ans = max(ans,s)s -= out cnt[out] -= 1if cnt[out] == 0:del cnt[out]return ans

 2461. 长度为 K 子数组中的最大和

给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：

• 子数组的长度是 k，且
• 子数组中的所有元素 各不相同 。

返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。

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

示例 1：

输入：nums = [1,5,4,2,9,9,9], k = 3
输出：15
解释：nums 中长度为 3 的子数组是：
- [1,5,4] 满足全部条件，和为 10 。
- [5,4,2] 满足全部条件，和为 11 。
- [4,2,9] 满足全部条件，和为 15 。
- [2,9,9] 不满足全部条件，因为元素 9 出现重复。
- [9,9,9] 不满足全部条件，因为元素 9 出现重复。
因为 15 是满足全部条件的所有子数组中的最大子数组和，所以返回 15 。

示例 2：

输入：nums = [4,4,4], k = 3
输出：0
解释：nums 中长度为 3 的子数组是：
- [4,4,4] 不满足全部条件，因为元素 4 出现重复。
因为不存在满足全部条件的子数组，所以返回 0 。

提示：

• 1 <= k <= nums.length <= 10**5
• 1 <= nums[i] <= 10**5

# 与2841题思路相似
class Solution:def maximumSubarraySum(self, nums: List[int], k: int) -> int:l = Counter(nums[:k - 1])n = len(nums)ans = 0sum1 = sum(nums[:k - 1])for i in range(k - 1,n):l[nums[i]] += 1sum1 += nums[i]if len(l) == k:ans = max(ans,sum1)l[nums[i - k + 1]] -= 1if l[nums[i - k + 1]] <= 0:del l[nums[i - k + 1]]sum1 -= nums[i - k + 1]return ans

 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:sum1 = sum(cardPoints[:k])ans = 0n = len(cardPoints)i = k - 1j = n - 1for o in range(k + 1):ans = max(sum1,ans)sum1 -= cardPoints[i]sum1 += cardPoints[j]i -= 1j -= 1return ans

 1297. 子串的最大出现次数

 

给你一个字符串 s ，请你返回满足以下条件且出现次数最大的 任意 子串的出现次数：

• 子串中不同字母的数目必须小于等于 maxLetters 。
• 子串的长度必须大于等于 minSize 且小于等于 maxSize 。

示例 1：

输入：s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
输出：2
解释：子串 "aab" 在原字符串中出现了 2 次。
它满足所有的要求：2 个不同的字母，长度为 3 （在 minSize 和 maxSize 范围内）。

示例 2：

输入：s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
输出：2
解释：子串 "aaa" 在原字符串中出现了 2 次，且它们有重叠部分。

示例 3：

输入：s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3
输出：3

示例 4：

输入：s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
输出：0

提示：

• 1 <= s.length <= 10^5
• 1 <= maxLetters <= 26
• 1 <= minSize <= maxSize <= min(26, s.length)
• s 只包含小写英文字母。

# 引用佬的一句话秒解"这题很明显maxSize没有用,因为长的串重复它的子串一定也重复”
class Solution:def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:dict1 = Counter(s[:minSize-1])dict2 = defaultdict(int)n = len(s)for i in range(minSize - 1,n):dict1[s[i]] += 1if len(dict1) <= maxLetters:dict2[s[i - minSize + 1:i + 1]] += 1dict1[s[i - minSize + 1]] -= 1if dict1[s[i - minSize + 1]] == 0:del dict1[s[i - minSize + 1]]return max(dict2.values()) if len(dict2) >= 1 else 0

 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 。

提示：

• n == nums.length 
• 1 <= n <= 10**5
• 1 <= k <= n
• 1 <= x <= k 
• -50 <= nums[i] <= 50 

class Solution:def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:cnt = [0] * 101for 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)):cnt[in_] += 1  # 进入窗口（保证窗口有恰好 k 个数）left = xfor j in range(-50, 0):  # 暴力枚举负数范围 [-50,-1]left -= cnt[j]if left <= 0:  # 找到美丽值ans[i] = jbreakcnt[out] -= 1  # 离开窗口return ans作者：灵茶山艾府
链接：https://leetcode.cn/problems/sliding-subarray-beauty/solutions/2241294/hua-dong-chuang-kou-bao-li-mei-ju-by-end-9mvl/
来源：力扣（LeetCode）

 2134. 最少交换次数来组合所有的 1 II

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

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

给你一个 二进制环形 数组 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 <= 10**5
• nums[i] 为 0 或者 1

class Solution:def minSwaps(self, nums: List[int]) -> int:k = nums.count(1)n = len(nums)dict1 = Counter(nums[:k - 1])ans = nums[:k].count(0)for i in range(k - 1,n + k):dict1[nums[i % n]] += 1    # 想要不不报错并且像环那样可以对数组长度取余ans = min(ans,dict1[0])dict1[nums[(i - k + 1) % n]] -= 1return ans

 567. 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的 

排列

。如果是，返回  true ；否则，返回  false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

示例 2：

输入：s1= "ab" s2 = "eidboaoo"
输出：false

提示：

• 1 <= s1.length, s2.length <= 10**4
• s1 和 s2 仅包含小写字母

class Solution:def checkInclusion(self, s1: str, s2: str) -> bool:k = len(s1)n = len(s2)dict1 = Counter(s1)dict2 = Counter(s2[:k - 1])for i in range(k - 1,n):dict2[s2[i]] += 1if dict1 == dict2: # python中字典可以对应判断是否相等return Truedict2[s2[i - k + 1]] -= 1if dict2[s2[i - k + 1]] == 0: # 窗口内已经没这个，就删去这个键del dict2[s2[i - k + 1]]return False

 438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 

异位词

 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

• 1 <= s.length, p.length <= 3 * 10**4
• s 和 p 仅包含小写字母

class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:s_len,p_len = len(s),len(p)if s_len < p_len:return []ans = []s_count = [0] * 26p_count = [0] * 26for i in range(p_len):s_count[ord(s[i]) - 97] += 1p_count[ord(p[i]) - 97] += 1if s_count == p_count:ans.append(0)for i in range(s_len - p_len):s_count[ord(s[i]) - 97] -= 1s_count[ord(s[i + p_len]) - 97] += 1if s_count == p_count:ans.append(i + 1)return ans

 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] <= 10**5

# 注意审题
class Solution:def minimumDifference(self, nums: List[int], k: int) -> int:nums.sort()e = float("inf")i = 0while k <= len(nums):e = min(e, nums[k - 1] - nums[i])i += 1k += 1if k == len(nums):e = min(e, nums[k - 1] - nums[i])print(k,i)breakreturn e

 感谢灵神的题单整理，以上是我做完题单之后的理解。