定长滑动窗口-基础

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

思路说明

本题是一个比较简单的滑动窗口，窗口的大小固定不变是K，要做的是判断窗口内元音字母的个数

首先我们构建一个变量用来统计当前窗口内元音字母的数量，设置为cnt

窗口只要不断向右滑动的，还需要一个变量存储所有经历过的窗口中元音字母数的最大值，也就是我们最后需要的结果，设置为ans

然后我们就是对字符串进行遍历

针对定长滑动窗口的类型，我们可以简单总结一个规律

先进行条件判断，修改对应变量值
判断窗口是否需要移动，如果移动修改对应值
判断窗口是否已经达到了固定长度，如果达到了，进行结果更新

一个简单的总结，仅供参考

针对我们现在的题目

创建一个变量记录当前窗口内元音字母的个数，设置为cnt
创建一个变量记录所有经历过的窗口内元音字母数最大值，设置为ans
然后进行遍历
- 先判断是不是元音字母，如果是窗口内元音字母个数cnt+1
- 然后判断窗口是否需要滑动，如果需要，判断最左边元素是不是元音字母，如果是cnt-1，如果不是，不需要进行更新
- 最后，判断当前窗口长度是不是达到要求，如果是，进行最大值的更新
返回最终结果ans

题解

package main

import "fmt"

func judge(ch byte) bool {
	if ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' {
		return true
	}

	return false
}

func maxVowels(s string, k int) int {
	ans := 0
	cnt := 0

	for i := 0; i < len(s); i++ {
		if judge(s[i]) {
			cnt++
		}
		if i >= k {
			if judge(s[i-k]) {
				cnt -= 1
			}
		}
		if i >= k-1 {
			ans = max(ans, cnt)
		}
	}

	return ans
}

func main() {
	testCases := []struct {
		s string
		k int
	}{
		{"abciiidef", 3},
		{"aeiou", 2},
		{"leetcode", 3},
		{"rhythms", 4},
		{"tryhard", 4},
	}

	for _, testCase := range testCases {
		fmt.Println(maxVowels(testCase.s, testCase.k))
	}
}

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

思路说明

构建长度为k的滑动窗口，设置变量计算窗口内数字的和，当窗口滑动的时候更新变量

设置变量动态更新最大平均数，注意这个变量初始化的时候设置成 math.MinInt

题解

// 643.子数组最大平均数I
package main

import (
	"fmt"
	"math"
)

func findMaxAverage(nums []int, k int) float64 {
	ans, cnt := math.MinInt, 0

	for i, num := range nums {
		cnt += num

		if i >= k {
			cnt -= nums[i-k]
		}

		if i >= k-1 {
			ans = max(ans, cnt)
		}
	}

	return float64(ans) / float64(k)
}

func main() {
	testCases := []struct {
		nums []int
		k    int
	}{
		{[]int{1, 12, -5, -6, 50, 3}, 4},
		{[]int{5}, 1},
	}

	for _, testCase := range testCases {
		fmt.Println(findMaxAverage(testCase.nums, testCase.k))
	}
}

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

思路说明

基本思路就是构建大小为k的窗口，计算窗口内元素的和，然后计算平均值是否大于等于某个阈值

还是按照咱们的步骤来

题解

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

import "fmt"

func numOfSubarrays(arr []int, k, threshold int) int {
	ans, cnt := 0, 0

	for i, num := range arr {
		cnt += num
		if i >= k {
			cnt -= arr[i-k]
		}

		if i >= k-1 && cnt >= k*threshold {
			ans += 1
		}
	}

	return ans
}

func main() {
	testCases := []struct {
		arr       []int
		k         int
		threshold int
	}{
		{[]int{2, 2, 2, 2, 5, 5, 5, 8}, 3, 4},
		{[]int{11, 13, 17, 23, 29, 31, 7, 5, 2, 3}, 3, 5},
	}

	for _, testCase := range testCases {
		fmt.Println(numOfSubarrays(testCase.arr, testCase.k, testCase.threshold))
	}
}

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

思路说明

本题提出了一个概念，半径为k的字数组

这个时候滑动窗口的实际大小是k * 2 + 1

之后能作为圆心的点才能够有平均值，其他的都是-1

所以，先设置答案存储的数组 ans 然后将全部的值初始化为-1

之后还是按照我们之前总结的思路来

题解

// 2090.半径为k的子数组平均值
package main

import "fmt"

func getAverages(nums []int, k int) []int {
	ans := make([]int, len(nums))

	for i := range ans {
		ans[i] = -1
	}

	cnt := 0

	for i, num := range nums {
		cnt += num

		if i >= 2*k {
			ans[i-k] = cnt / (k*2 + 1)
			cnt -= nums[i-2*k]
		}
	}

	return ans
}

func main() {
	testCases := []struct {
		nums []int
		k    int
	}{
		{[]int{7, 4, 3, 9, 1, 8, 5, 2, 6}, 3},
		{[]int{100000}, 0},
		{[]int{8}, 100000},
	}

	for _, testCase := range testCases {
		fmt.Println(getAverages(testCase.nums, testCase.k))
	}
}

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

思路说明

我们需要的是K个连续的黑色块，也就是把大小为k的窗口中的白色块全部涂黑

我们要到这个最小的涂色数，也是黑色块最多，白色块最少

我们找到黑色块最多的然后用k减去这个数量即可

题解

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

import "fmt"

func minimumRecolors(blocks string, k int) int {
	ans, cnt := 0, 0

	for i, block := range blocks {
		if block == 'B' {
			cnt += 1
		}

		if i >= k {
			if blocks[i-k] == 'B' {
				cnt -= 1
			}
		}

		if i >= k-1 {
			ans = max(ans, cnt)
		}
	}

	return k - ans
}

func main() {
	testCases := []struct {
		blocks string
		k      int
	}{
		{"WBBWWBBWBW", 7},
		{"WBWBBBW", 2},
	}

	for _, testCase := range testCases {
		fmt.Println(minimumRecolors(testCase.blocks, testCase.k))
	}
}

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

思路说明

从这道题开始引入一个变量，开始对窗口中元素的数量进行控制

对数量的统计和控制可以通过引入哈希表实现，在golang中，我们可以使用map[type]type 来表示哈希表

通过map[num]可以统计num的数量，通过len(map)可以控制元素的种类，这也是最常用的两种方式

在本题中，我们要把len(map)控制在m以内

然后其他的逻辑都是固定的

题解

// 2841.几乎唯一子数组的最大和
package main

import "fmt"

func maxSum(nums []int, m, k int) int64 {
	mp := make(map[int]int)
	var ans, cnt int64
	for i, num := range nums {
		cnt += int64(num)
		mp[num] += 1

		if i >= k {
			cnt -= int64(nums[i-k])
			mp[nums[i-k]] -= 1
			if mp[nums[i-k]] == 0 {
				delete(mp, nums[i-k])
			}
		}

		if i >= k-1 && len(mp) >= m {
			ans = max(ans, cnt)
		}
	}

	return ans
}

func main() {
	testCases := []struct {
		nums []int
		m    int
		k    int
	}{
		{[]int{2, 6, 7, 3, 1, 7}, 3, 4},
		{[]int{5, 9, 9, 2, 4, 5, 4}, 1, 3},
		{[]int{1, 2, 1, 2, 1, 2, 1}, 3, 3},
	}

	for _, testCase := range testCases {
		fmt.Println(maxSum(testCase.nums, testCase.m, testCase.k))
	}
}

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

思路说明

通过哈希表大小控制所有元素各不相同的要求，通过滑动窗口控制字数组的长度k

题解

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

import "fmt"

func maximumSubarraySum(nums []int, k int) int64 {
	mp := make(map[int]int)
	var ans, cnt int64

	for i, num := range nums {
		cnt += int64(num)
		mp[num] += 1

		if i >= k {
			cnt -= int64(nums[i-k])
			mp[nums[i-k]] -= 1
			if mp[nums[i-k]] == 0 {
				delete(mp, nums[i-k])
			}

		}

		if i >= k-1 && len(mp) == k {
			ans = max(ans, cnt)
		}
	}

	return ans
}

func main() {
	testCases := []struct {
		nums []int
		k    int
	}{
		{[]int{1, 5, 4, 2, 9, 9, 9}, 3},
		{[]int{4, 4, 4}, 3},
	}

	for _, testCase := range testCases {
		fmt.Println(maximumSubarraySum(testCase.nums, testCase.k))
	}
}

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

思路说明

这道题同样归类于滑动窗口，它是首尾构成一个滑动窗口

我的做法现在数组首部构建一个长度为k的滑动窗口

然后移动窗口开始尾部移动，直到尾部移动k

题解

// 1423.可获得的最大点数
package main

import "fmt"

func maxScore(cardPoints []int, k int) int {
	left := k - 1
	ans, cnt := 0, 0

	for i := 0; i < k; i++ {
		cnt += cardPoints[i]
	}

	ans = cnt

	for i := len(cardPoints) - 1; i >= len(cardPoints)-k; i-- {
		cnt -= cardPoints[left]
		left -= 1
		cnt += cardPoints[i]

		ans = max(ans, cnt)
	}

	return ans
}

func main() {
	testCases := []struct {
		nums []int
		k    int
	}{
		{[]int{1, 2, 3, 4, 5, 6, 1}, 3},
		{[]int{2, 2, 2}, 2},
		{[]int{9, 7, 7, 9, 7, 7, 9}, 7},
		{[]int{1, 1000, 1}, 1},
		{[]int{1, 79, 80, 1, 1, 1, 200, 1}, 3},
	}

	for _, testCase := range testCases {
		fmt.Println(maxSore(testCase.nums, testCase.k))
	}
}

1176. 健身计划评估

题面

你的好友是一位健身爱好者。前段日子，他给自己制定了一份健身计划。现在想请你帮他评估一下这份计划是否合理。

他会有一份计划消耗的卡路里表，其中 calories[i] 给出了你的这位好友在第 i 天需要消耗的卡路里总量。

为了更好地评估这份计划，对于卡路里表中的每一天，你都需要计算他「这一天以及之后的连续几天」（共 k 天）内消耗的总卡路里 T：

如果 T < lower，那么这份计划相对糟糕，并失去 1 分；

如果 T > upper，那么这份计划相对优秀，并获得 1 分；

否则，这份计划普普通通，分值不做变动。

请返回统计完所有 calories.length 天后得到的总分作为评估结果。

注意：总分可能是负数。

示例 1：

输入：calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3

输出：0

解释：calories[0], calories[1] < lower 而 calories[3], calories[4] > upper, 总分 = 0.

示例 2：

输入：calories = [3,2], k = 2, lower = 0, upper = 1

输出：1

解释：calories[0] + calories[1] > upper, 总分 = 1.

示例 3：

输入：calories = [6,5,0,0], k = 2, lower = 1, upper = 5

输出：0

解释：calories[0] + calories[1] > upper, calories[2] + calories[3] < lower, 总分 = 0.

提示：

1 <= k <= calories.length <= 10^5

0 <= calories[i] <= 20000

0 <= lower <= upper

思路说明

构建滑动窗口，统计窗口中消耗的卡路里，然后判断

基本思路还是按照之前的步骤

题解

// 1176.健身计划评估
package main

import "fmt"

func dietPlanPerformance(calories []int, k, lower, upper int) int {
	ans, cnt := 0, 0

	for i, calorie := range calories {
		cnt += calorie

		if i >= k {
			cnt -= calories[i-k]
		}

		if i >= k-1 {
			if cnt > upper {
				ans += 1
			}

			if cnt < lower {
				ans -= 1
			}
		}
	}

	return ans
}

func main() {
	testCases := []struct {
		calories []int
		k        int
		lower    int
		upper    int
	}{
		{[]int{1, 2, 3, 4, 5}, 1, 3, 3},
		{[]int{3, 2}, 2, 0, 1},
		{[]int{6, 5, 0, 0}, 2, 1, 5},
	}

	for _, testCase := range testCases {
		fmt.Println(dietPlanPerformance(testCase.calories, testCase.k, testCase.lower, testCase.upper))
	}
}

1100. 长度为 K 的无重复字符子串

题面

给你一个字符串 S，找出所有长度为 K 且不含重复字符的子串，请你返回全部满足要求的子串的数目。

示例 1：

输入：S = “havefunonleetcode”, K = 5

输出：6

解释：这里有 6 个满足题意的子串，分别是：‘havef’,‘avefu’,‘vefun’,‘efuno’,‘etcod’,‘tcode’。

示例 2：

输入：S = “home”, K = 5

输出：0

解释：注意：K 可能会大于 S 的长度。在这种情况下，就无法找到任何长度为 K 的子串。

提示：

1 <= S.length <= 10^4

S 中的所有字符均为小写英文字母

1 <= K <= 10^4

思路说明

使用哈希表控制字符串是否重复

使用滑动窗口构建长度为k的子串

题解

// 1100.长度为K的无重复字符子串
package main

import "fmt"

func numKLenSubstrNoRepeats(s string, k int) int {
	mp := make(map[byte]int)
	ans := 0

	for i := 0; i < len(s); i++ {
		mp[s[i]] += 1

		if i >= k {
			mp[s[i-k]] -= 1
			if mp[s[i-k]] == 0 {
				delete(mp, s[i-k])
			}
		}

		if i >= k-1 && len(mp) == k {
			ans += 1
		}
	}

	return ans
}

func main() {
	testCases := []struct {
		s string
		k int
	}{
		{"havefunonleetcode", 5},
		{"home", 5},
	}

	for _, testCase := range testCases {
		fmt.Println(numKLenSubstrNoRepeats(testCase.s, testCase.k))
	}
}

1852. 每个子数组的数字种类数

题面

给你一个长度为 n 的整数数组 nums 与一个整数 k。你的任务是找到 nums 所有长度为 k 的子数组中不同元素的数量。

返回一个数组 ans，其中 ans[i] 是对于每个索引 0 <= i < n - k，nums[i..(i + k - 1)] 中不同元素的数量。

示例 1:

输入: nums = [1,2,3,2,2,1,3], k = 3

输出: [3,2,2,2,3]

解释：每个子数组的数字种类计算方法如下：

nums[0..2] = [1,2,3] 所以 ans[0] = 3
nums[1..3] = [2,3,2] 所以 ans[1] = 2
nums[2..4] = [3,2,2] 所以 ans[2] = 2
nums[3..5] = [2,2,1] 所以 ans[3] = 2
nums[4..6] = [2,1,3] 所以 ans[4] = 3

示例 2:

输入: nums = [1,1,1,1,2,3,4], k = 4

输出: [1,2,3,4]

解释: 每个子数组的数字种类计算方法如下：

nums[0..3] = [1,1,1,1] 所以 ans[0] = 1
nums[1..4] = [1,1,1,2] 所以 ans[1] = 2
nums[2..5] = [1,1,2,3] 所以 ans[2] = 3
nums[3..6] = [1,2,3,4] 所以 ans[3] = 4

提示:

1 <= k <= nums.length <= 10^5

1 <= nums[i] <= 10^5

思路说明

构建滑动窗口，长度固定为k

使用哈希表记录一下窗口内数字的种类，并实时更新

题解

// 1852.每个子数组的数字种类数
package main

import "fmt"

func distinctNumbers(nums []int, k int) []int {
	mp := make(map[int]int)
	ans := make([]int, len(nums)-k+1)

	for i, num := range nums {
		mp[num] += 1

		if i >= k {
			mp[nums[i-k]] -= 1
			if mp[nums[i-k]] == 0 {
				delete(mp, nums[i-k])
			}
		}

		if i >= k-1 {
			ans[i-k+1] = len(mp)
		}
	}

	return ans
}

func main() {
	testCases := []struct {
		nums []int
		k    int
	}{
		{[]int{1, 2, 3, 2, 2, 1, 3}, 3},
		{[]int{1, 1, 1, 1, 2, 3, 4}, 4},
	}

	for _, testCase := range testCases {
		fmt.Println(distinctNumbers(testCase.nums, testCase.k))
	}
}

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

题面

给出一个二进制数组 data，你需要通过交换位置，将数组中任何位置上的 1 组合到一起，并返回所有可能中所需最少的交换次数。

示例 1:

输入: data = [1,0,1,0,1]

输出: 1

解释:

有三种可能的方法可以把所有的 1 组合在一起：

[1,1,1,0,0]，交换 1 次；

[0,1,1,1,0]，交换 2 次；

[0,0,1,1,1]，交换 1 次。

所以最少的交换次数为 1。

示例 2:

输入：data = [0,0,0,1,0]

输出：0

解释：

由于数组中只有一个 1，所以不需要交换。

示例 3:

输入：data = [1,0,1,0,1,0,0,1,1,0,1]

输出：3

解释：

交换 3 次，一种可行的只用 3 次交换的解决方案是 [0,0,0,0,0,1,1,1,1,1,1]。

示例 4:

输入: data = [1,0,1,0,1,0,1,1,1,0,1,0,0,1,1,1,0,0,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,1]

输出: 8

提示:

1 <= data.length <= 10^5

data[i] == 0 or 1.

思路说明

题目的要求是把所有的1都组合在一起，并返回所需要的最少交换次数

我们首先需要知道数组中1的个数，将这个数量作为滑动窗口的大小

我们已经得到滑动窗口的大小，然后统计窗口中最大的1的数量，用窗口大小减去这个最大值，就是我们需要的最少交换次数

题解

// 1151.最少交换次数来组合所有的1
package main

import "fmt"

func minSwaps(data []int) int {
	k := 0 // 滑动窗口的大小
	for _, val := range data {
		k += val
	}

	ans, cnt := 0, 0

	for i, val := range data {
		cnt += val

		if i >= k {
			cnt -= data[i-k]
		}

		if i >= k-1 {
			ans = max(ans, cnt)
		}
	}

	return k - ans
}

func main() {
	testCases := [][]int{
		[]int{1, 0, 1, 0, 1},
		[]int{0, 0, 0, 1, 0},
		[]int{1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1},
		[]int{1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1},
	}

	for _, testCase := range testCases {
		fmt.Println(minSwaps(testCase))
	}
}

2107. 分享 K 个糖果后独特口味的数量

题面

您将获得一个从0开始的整数数组 candies ，其中 candies[i] 表示第 i 个糖果的味道。你妈妈想让你和你妹妹分享这些糖果，给她 k 个连续的糖果，但你想保留尽可能多的糖果口味。

在与妹妹分享后，返回最多可保留的独特口味的糖果。

示例 1：

输入: candies = [1,2,2,3,4,3], k = 3

输出: 3

解释: 将[1,3]（含[2,2,3]）范围内的糖果加入[2,2,3]口味。你可以吃各种口味的糖果[1,4,3]。有3种独特的口味，所以返回3。

示例 2:

输入: candies = [2,2,2,2,3,3], k = 2

输出: 2

解释: 在[3,4]范围内（含[2,3]）的糖果中加入[2,3]口味。你可以吃各种口味的糖果[2,2,2,3]。有两种独特的口味，所以返回2。请注意，你也可以分享口味为[2,2]的糖果，吃口味为[2,2,3,3]的糖果。

示例 3:

输入: candies = [2,4,5], k = 0

输出: 3

解释: 你不必给任何糖果。你可以吃各种口味的糖果[2,4,5]。有3种独特的口味，所以返回3。

提示:

0 <= candies.length <= 10^5

1 <= candies[i] <= 10^5

0 <= k <= candies.length

思路说明

这个题目比较特殊，是要构建一个连续数组，数组长度为k，删除这个数组后剩余的数字种类尽量多

这样就使用哈希表存储剩余种类和对应数量即可

还是按照三步进行即可

题解

// 2107.分享K个糖果后独特口味的数量
package main

import "fmt"

func shareCandies(candies []int, k int) int {
	mp := make(map[int]int)
	ans := 0

	for _, candie := range candies {
		mp[candie] += 1
	}

	for i, candie := range candies {
		mp[candie] -= 1

		if mp[candie] == 0 {
			delete(mp, candie)
		}

		if i >= k {
			mp[candies[i-k]] += 1
		}

		if i >= k-1 {
			ans = max(ans, len(mp))
		}
	}

	return ans
}

func main() {
	testCases := []struct {
		candies []int
		k       int
	}{
		{[]int{1, 2, 2, 3, 4, 3}, 3},
		{[]int{2, 2, 2, 2, 3, 3}, 2},
		{[]int{2, 4, 5}, 0},
	}

	for _, testCase := range testCases {
		fmt.Println(shareCandies(testCase.candies, testCase.k))
	}
}

定长滑动窗口-基础

题面

思路说明

题解

题面

思路说明

题解

题面

思路说明

题解

题面

思路说明

题解

题面

思路说明

题解

题面

思路说明

题解

题面

思路说明

题解

题面

思路说明

题解

题面

思路说明

题解

题面

思路说明

题解

题面

思路说明

题解

题面

思路说明

题解

题面

思路说明

题解

同一系列 · 滑动窗口与双指针

继续阅读