题目都摘选自灵神题单
定长滑窗题目
定长滑窗套路
总结成三步：入-更新-出。
- 入：下标为 i 的元素进入窗口，更新相关统计量。如果 i<k−1 则重复第一步。
- 更新：更新答案。一般是更新最大值/最小值。
- 出：下标为 i−k+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^5s由小写英文字母组成1 <= k <= s.length
func maxVowels(s string, k int) int {vowel := 0ans := -1;for i := 0; i < len(s); i++ {// 1. 进入窗口if s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u' {vowel++}// i < k - 1 指窗口刚好填满剩一个，这样下一个循环进来窗口刚好填满。 刚好更新的时候是窗口满了的时候 计算出的答案。 然后末尾再挪出窗口最左边元素if i < k - 1 {continue}// 更新窗口if vowel > ans {ans = vowel}// 离开窗口out := s[i - k + 1]if out == 'a' || out == 'e' || out == 'i' || out == 'o' || out == 'u' {vowel--}}return ans
}
643 子数组平均数最大值
给你一个由 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
func findMaxAverage(nums []int, k int) float64 {res := -1e4 - 1sum := 0for i, in := range nums {// 入窗sum += inif i < k - 1 {continue}// 更新avg := float64(sum) / float64(k)if avg > res {res = avg}// 出窗sum -= nums[i - k + 1]}return res}
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 <= 1051 <= arr[i] <= 1041 <= k <= arr.length0 <= threshold <= 104
func numOfSubarrays(arr []int, k int, threshold int) int {res := 0windowSum := 0for i, in := range arr {windowSum += inif i < k - 1 {continue}if windowSum >= threshold {res++}windowSum -= arr[i - k + 1]}return res
}
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 。
func getAverages(nums []int, k int) []int {res := make([]int, len(nums))windowSum := 0windowLen := 2 * k + 1for i := 0; i < len(res); i++ {res[i] = -1}for i, in := range nums {windowSum += inif i < windowLen - 1 {continue}res[i - k] = windowSum / windowLenwindowSum -= nums[i - windowLen + 1]}return res
}
2379 得到K个黑块的最少涂色次数
给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 'W' 要么是 'B' ，表示第 i 块的颜色。字符 'W' 和 'B' 分别表示白色和黑色。
给你一个整数 k ，表示想要 连续 黑色块的数目。
每一次操作中，你可以选择一个白色块将它 涂成 黑色块。
请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数。
func minimumRecolors(blocks string, k int) int {// 定长滑窗 k为窗口大小，每次统计K个里面 W的个数，选一个最少的ans := math.MaxIntwhiteCnt := 0for i, in := range blocks {// 入窗if in == 'W' {whiteCnt++}// 还没入满K个if i < k - 1 {continue}if whiteCnt < ans {ans = whiteCnt}// 出窗if blocks[i - k + 1] == 'W' {whiteCnt--}}return ans
}
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 是负数，那么和为 之前 的数字。
func decrypt(code []int, k int) []int {// 定长滑窗 k > 0 时候就正常 长度为K的窗口，每次更新窗口左边的值// k==0的时候类似，只不过更新的值为0// k < 0 滑动长度为K的窗口，每次更新窗口右边边的值, 返回结果的时候再反转// 循环怎么办 n = len(code) 入窗的 元素为 code[(n + i) % n] i < n + windowLenres := make([]int, len(code))if k == 0 {return res}windowLen := kn := len(code)if k < 0 {windowLen = -k}windowSum := 0for i := 0; i < n + windowLen; i++ {// 入窗windowSum += code[(i + n) % n]if i < windowLen - 1 {continue}if k > 0 {res[(n + i - windowLen) % n] = windowSum} else {res[(n + i + 1) % n] = windowSum}windowSum -= code[(n + i - windowLen + 1) % n]}return res
}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.length1 <= minutes <= n <= 2 * 1040 <= customers[i] <= 1000grumpy[i] == 0 or 1
func maxSatisfied(customers []int, grumpy []int, minutes int) int {// 第i分钟开始，第i分钟后离开。那么先用grumpy判断第i分钟哪些客户不满意。再用minutes长度的窗口取滑动这个不满意数组。统计最大值呗// 或者只遍历一次，答案由两部分组成，本来就满意的，和纠正满意的。窗口内只统计纠正满意的总和。取总和最大的ans := 0windowSum := 0maxWindowSum := math.MinIntfor i, in := range customers {if grumpy[i] == 0 {ans += in} else {windowSum += in}if i < minutes - 1 {continue}fmt.Println(ans, windowSum)if windowSum > maxWindowSum {// 纠正满意度最大值maxWindowSum = windowSum}if grumpy[i - minutes + 1] == 1 {windowSum -= customers[i - minutes + 1]}}return ans + maxWindowSum
}
1461 检查一个字符串是否包含所有长度为K的二进制子串
给你一个二进制字符串 s 和一个整数 k 。如果所有长度为 k 的二进制字符串都是 s 的子串，请返回 true ，否则请返回 false 。
示例 1：
输入：s = "00110110", k = 2
输出：true
解释：长度为 2 的二进制串包括 "00"，"01"，"10" 和 "11"。它们分别是 s 中下标为 0，1，3，2 开始的长度为 2 的子串。
示例 2：
输入：s = "0110", k = 1
输出：true
解释：长度为 1 的二进制串包括 "0" 和 "1"，显然它们都是 s 的子串。
示例 3：
输入：s = "0110", k = 2
输出：false
解释：长度为 2 的二进制串 "00" 没有出现在 s 中。
提示：
1 <= s.length <= 5 * 105s[i]不是'0'就是'1'1 <= k <= 20
func hasAllCodes(s string, k int) bool {// 用长度为2 ^ k的数组缓存每个二进制数是否存在// 定长滑窗 k 。 每次更新对组成的二进制串计算十进制值 然后km := make([]int, 1 << k)//windowValues := []byte{}for i := 0 ; i < len(s); i++ {// 入窗//windowValues = append(windowValues, s[i])if i < k - 1 {continue}idx, _ := strconv.ParseInt(s[i - k + 1: i + 1], 2, 32)km[idx] = 1// 出窗//windowValues = windowValues[1:]}for _, v := range km {if v != 1 {return false}}return true
}
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 * 1041 <= m <= k <= nums.length1 <= nums[i] <= 109
func maxSum(nums []int, m int, k int) int64 {// 定长滑窗，对窗口内的做唯一子数组判断 和总和最大值更新// map记录窗口内数字数量，归0了就删var sum int64 = 0var ans int64 = 0mm := make(map[int]int, 0)for i, in := range nums {// 入窗sum += int64(in)if _, ok := mm[in]; ok {mm[in]++} else {mm[in] = 1}if i < k - 1 {continue}if len(mm) >= m && ans < sum{ans = sum}// 出窗out := nums[i - k + 1]sum -= int64(out)if _, ok := mm[out]; ok {mm[out]--if mm[out] == 0 {delete(mm, 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 <= 1051 <= nums[i] <= 105
func maximumSubarraySum(nums []int, k int) int64 {// 和2841一样// 定长滑窗，对窗口内的做唯一子数组判断 和总和最大值更新// map记录窗口内数字数量，归0了就删var sum int64 = 0var ans int64 = 0mm := make(map[int]int, 0)for i, in := range nums {// 入窗sum += int64(in)if _, ok := mm[in]; ok {mm[in]++} else {mm[in] = 1}if i < k - 1 {continue}if len(mm) >= k && ans < sum{ans = sum}// 出窗out := nums[i - k + 1]sum -= int64(out)if _, ok := mm[out]; ok {mm[out]--if mm[out] == 0 {delete(mm, out)}}}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^51 <= cardPoints[i] <= 10^41 <= k <= cardPoints.length
func maxScore(cardPoints []int, k int) int {// 拿走K张，剩下n-k必须是连续的。为了拿走的牌值最大，那么剩下的牌的总和就尽可能小// 转化为n-k窗口求内总和值最小。 然后返回总和-窗口最小值windowLen := len(cardPoints) - kwinMinSum := math.MaxIntsum := 0totalSum := 0for i, in := range cardPoints {totalSum += in// 入窗sum += in// 存在全拿的情况if windowLen == 0 || i < windowLen - 1 {continue}// 更新if sum < winMinSum {winMinSum = sum}sum -= cardPoints[i - windowLen + 1]}if windowLen == 0 {winMinSum = 0}return totalSum - winMinSum
}
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^51 <= maxLetters <= 261 <= minSize <= maxSize <= min(26, s.length)s只包含小写英文字母。
func maxFreq(s string, maxLetters int, minSize int, maxSize int) int {// 题目需要的不同字母的数目小于等于maxLetters，长度大于等于minSize且小于等于maxSize的子串。// 用哈希表统计子串出现最大次数// 本题只需统计长度为minSize的子串，而不需要统计长度为maxSize的子串。因为长的肯定会覆盖短的。 同时子串需要满足不同字母数小于等于maxLetters// minSize=2 maxSize = 3 abc 如果满足答案 那么 ab肯定也满足答案, 那只用统计短的就好。如果abc出现两次，那ab肯定至少出现了两次以上mm := make(map[string]int)wm := make(map[byte]int)ans := 0for i := 0; i < len(s); i++ {// 入窗 无需操作if _, ok := wm[s[i]]; ok {wm[s[i]]++} else {wm[s[i]] = 1}if i < minSize - 1 {continue}// 更新sw := s[i - minSize + 1: i + 1]if _, ok := mm[sw]; ok {mm[sw]++} else {mm[sw] = 1}if len(wm) <= maxLetters && mm[sw] > ans {ans = mm[sw]}// 出窗wm[s[i - minSize + 1]]--if wm[s[i - minSize + 1]] == 0 {delete(wm, s[i - minSize + 1])}}return ans;
}
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.length1 <= n <= 1051 <= k <= n1 <= x <= k-50 <= nums[i] <= 50
func getSubarrayBeauty(nums []int, k int, x int) []int {// 定长滑窗// 主要是看怎么快速找到第k小的数。值域很小，可以用计数排序 cnt统计数量。然后对窗口内的Cnt数组暴力遍历diff := 50cnt := make([]int, 101)ans := make([]int, 0)for i, in := range nums {cnt[in + diff]++if i < k - 1 {continue}// 遍历负数 0~49 对应 -50 ~ -1nx := 0haveBeauty := falsefor j := 0; j < diff; j++ {nx += cnt[j]if nx >= x {ans = append(ans, j - diff)haveBeauty = truebreak}}if !haveBeauty {ans = append(ans, 0)}// 出窗cnt[nums[i - k + 1] + diff]--}return ans
}
