定长滑动窗口-越长越合法/求最短/最小

209. 长度最小的子数组

题面

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]

输出：2

解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]

输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]

输出：0

提示：

1 <= target <= 10^9

1 <= nums.length <= 10^5

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

思路说明

采用双指针变长滑动窗口的思路

设定左指针，控制窗口大小，遍历数组的index作为右指针

设置变量统计窗口内的数字和

当数字和达到要求的时候

• 采用while循环
• 更新字数组的最小值
• 将左边的值排除窗口，更新数字和，同时将左指针向右移动
• 直到数字和不满足要求结束循环

题解

// 209.长度最小的子数组
package main

import (
	"fmt"
	"math"
)

func minSubArrayLen(target int, nums []int) int {
	ans, left := math.MaxInt, 0
	cnt := 0

	for i, num := range nums {
		cnt += num
		for cnt >= target {
			ans = min(ans, i-left+1)
			cnt -= nums[left]
			left += 1
		}
	}

	if ans > len(nums) {
		return 0
	} else {
		return ans
	}
}

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

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

2904. 最短且字典序最小的美丽子字符串

题面

给你一个二进制字符串 s 和一个正整数 k 。

如果 s 的某个子字符串中 1 的个数恰好等于 k ，则称这个子字符串是一个 美丽子字符串 。

令 len 等于 最短 美丽子字符串的长度。

返回长度等于 len 且字典序 最小 的美丽子字符串。如果 s 中不含美丽子字符串，则返回一个 空 字符串。

对于相同长度的两个字符串 a 和 b ，如果在 a 和 b 出现不同的第一个位置上，a 中该位置上的字符严格大于 b 中的对应字符，则认为字符串 a 字典序 大于 字符串 b 。

例如，“abcd” 的字典序大于 “abcc” ，因为两个字符串出现不同的第一个位置对应第四个字符，而 d 大于 c 。

示例 1：

输入：s = “100011001”, k = 3

输出：“11001”

解释：示例中共有 7 个美丽子字符串：

1. 子字符串 “100011001” 。
2. 子字符串 “100011001” 。
3. 子字符串 “100011001” 。
4. 子字符串 “100011001” 。
5. 子字符串 “100011001” 。
6. 子字符串 “100011001” 。
7. 子字符串 “100011001” 。

最短美丽子字符串的长度是 5 。

长度为 5 且字典序最小的美丽子字符串是子字符串 “11001” 。

示例 2：

输入：s = “1011”, k = 2

输出：“11”

解释：示例中共有 3 个美丽子字符串：

1. 子字符串 “1011” 。
2. 子字符串 “1011” 。
3. 子字符串 “1011” 。

最短美丽子字符串的长度是 2 。

长度为 2 且字典序最小的美丽子字符串是子字符串 “11” 。

示例 3：

输入：s = “000”, k = 1

输出：""

解释：示例中不存在美丽子字符串。

提示：

1 <= s.length <= 100

1 <= k <= s.length

思路说明

我们要做的是找到一个子字符串，子字符串中1的数量为看，如果有多个答案，返回字典序最小的那个

首先根据题目，当字符串中1的数量小于k的时候，会返回空字符串，直接返回

然后初始化结果ans为输入字符串s，因为最差的结果就是s，所以设置为s

之后设置cnt表示窗口内1的数量，left表示窗口的左边界，用循环的index表示右边界

每次移动右边界之后

• 判断窗口内1的数量是不是达到要求
• 如果达到了，开始移动左边界，直到把最左边的1排出
• 这个过程中，左边可能有很多0，排出之后会减小子字符串的长度，所以不断更新子字符串以及左边界，这是还要注意子字符串长度相同选最小字典序的情况
• 这个过程通过while循环实现

题解

// 2904.最短且字典序最小的美丽子字符串
package main

import (
	"fmt"
	"strings"
)

func shortestBeautifulSubstring(s string, k int) string {
	if strings.Count(s, "1") < k {
		return ""
	}
	ans := s
	cnt, left := 0, 0

	for i, ch := range s {
		if ch == '1' {
			cnt += 1
		}

		for cnt >= k {
			tmp := s[left : i+1]
			if s[left] == '1' {
				cnt -= 1
			}
			left += 1
			if len(tmp) == len(ans) {
				if tmp < ans {
					ans = tmp
				}
			}
			if len(tmp) < len(ans) {
				ans = tmp
			}
		}
	}

	return ans
}

func main() {
	testCases := []struct {
		s string
		k int
	}{
		{"100011001", 3},
		{"1011", 2},
		{"000", 1},
	}

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

1234. 替换子串得到平衡字符串

题面

有一个只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符，且长度为 n 的字符串。

假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。

给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。

你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。

请返回待替换子串的最小可能长度。

如果原字符串自身就是一个平衡字符串，则返回 0。

示例 1：

输入：s = “QWER”

输出：0

解释：s 已经是平衡的了。

示例 2：

输入：s = “QQWE”

输出：1

解释：我们需要把一个 ‘Q’ 替换成 ‘R’，这样得到的 “RQWE” (或 “QRWE”) 是平衡的。

示例 3：

输入：s = “QQQW”

输出：2

解释：我们可以把前面的 “QQ” 替换成 “ER”。

示例 4：

输入：s = “QQQQ”

输出：3

解释：我们可以替换后 3 个 ‘Q’，使 s = “QWER”。

提示：

1 <= s.length <= 10^5

s.length 是 4 的倍数

s 中只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符

思路说明

构建一个最小窗口，让窗口外的每种字符数量尽量接近n，这个最小窗口就是需要替换的字符串

通过哈希表统计每种字符的数量

题解

// 1234.替换子串得到平衡字符串
package main

import "fmt"

func balancedString(s string) int {
	// 构建哈希表，统计各自的数量
	// 构建一个最小窗口，让窗口外的每种字符数量尽量接近n，这个最小窗口就是需要替换的字符串
	mp := make(map[byte]int, 4)
	n := len(s) / 4

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

	// 已经平衡，返回0
	if mp['Q'] == n && mp['W'] == n && mp['E'] == n && mp['R'] == n {
		return 0
	}

	ans, left := len(s), 0

	for i := 0; i < len(s); i++ {
		mp[s[i]] -= 1 // 放进窗口
		for mp['Q'] <= n && mp['W'] <= n && mp['E'] <= n && mp['R'] <= n {
			// 满足条件，记录并收缩
			ans = min(ans, i-left+1)
			mp[s[left]] += 1
			left += 1
		}
	}

	return ans
}

func main() {
	testCases := []string{
		"QWER",
		"QQWE",
		"QQQW",
		"QQQQ",
	}

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

2875. 无限数组的最短子数组

题面

给你一个下标从 0 开始的数组 nums 和一个整数 target 。

下标从 0 开始的数组 infinite_nums 是通过无限地将 nums 的元素追加到自己之后生成的。

请你从 infinite_nums 中找出满足 元素和 等于 target 的 最短 子数组，并返回该子数组的长度。如果不存在满足条件的子数组，返回 -1 。

示例 1：

输入：nums = [1,2,3], target = 5

输出：2

解释：在这个例子中 infinite_nums = [1,2,3,1,2,3,1,2,…] 。

区间 [1,2] 内的子数组的元素和等于 target = 5 ，且长度 length = 2 。

可以证明，当元素和等于目标值 target = 5 时，2 是子数组的最短长度。

示例 2：

输入：nums = [1,1,1,2,3], target = 4

输出：2

解释：在这个例子中 infinite_nums = [1,1,1,2,3,1,1,1,2,3,1,1,…].

区间 [4,5] 内的子数组的元素和等于 target = 4 ，且长度 length = 2 。

可以证明，当元素和等于目标值 target = 4 时，2 是子数组的最短长度。

示例 3：

输入：nums = [2,4,6,8], target = 3

输出：-1

解释：在这个例子中 infinite_nums = [2,4,6,8,2,4,6,8,…] 。

可以证明，不存在元素和等于目标值 target = 3 的子数组。

提示：

1 <= nums.length <= 10^5

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

1 <= target <= 10^9

思路说明

使用的nuns的数量是不不定的，可能是1-n个，但是可以观察到，如果使用n个，中间n-2个是完整的，左边nums和右边nums，分别取右边和左边连续的数据

设 nums的数据和事total

target = total*m + res

res = nums*2[i:j]

我们要做的就是找到res的长度

res = target & total

其他的按照固定步骤做即可

题解

// 2875.无限数组的最短子数组
package main

import (
	"fmt"
	"math"
)

func minSizeSubarray(nums []int, target int) int {
	total := 0
	for _, x := range nums {
		total += x
	}

	ans := math.MaxInt
	left, sum, n := 0, 0, len(nums)
	for right := 0; right < n*2; right++ {
		sum += nums[right%n]
		for sum > target%total {
			sum -= nums[left%n]
			left++
		}
		if sum == target%total {
			ans = min(ans, right-left+1)
		}
	}
	if ans == math.MaxInt {
		return -1
	}
	return ans + target/total*n
}

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

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

76. 最小覆盖子串

题面

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC”

输出：“BANC”

解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。

示例 2：

输入：s = “a”, t = “a”

输出：“a”

解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = “a”, t = “aa”

输出: ""

解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，

因此没有符合条件的子字符串，返回空字符串。

提示：

m == s.length

n == t.length

1 <= m, n <= 10^5

s 和 t 由英文字母组成

思路说明

先说一下题目的要求，找到s的子串，子串包含t中所有字符（种类和数量）

首先，我们要知道t中有哪些字符

然后，在s中找到子串，子串中包含t中所有种类字符，这个子串尽可能小

所以使用哈希表统计t中所有字符种类和数量

然后在s中找子串，如果子串中字符在哈希表中，就减去，如果哈希表全部变成0，表示子串中已经包含t中全部字符，然后缩小窗口，直到不满足要求

题解

// 76.最小覆盖子串
package main

import (
	"fmt"
	"math"
)

func minWindow(s string, t string) string {
	// 先统计一下t中各个字符的数量,统计一下字符的种类
	mp := make(map[byte]int)

	for i := 0; i < len(t); i++ {
		mp[t[i]] += 1
	}
	left := 0
	cnt := len(mp) // 字符的种类
	ans := ""
	tmp := math.MaxInt

	for i := 0; i < len(s); i++ {
		if _, ok := mp[s[i]]; ok { // 字符有效
			mp[s[i]] -= 1
			if mp[s[i]] == 0 { // 符合要求
				cnt -= 1
			}
		}

		for cnt == 0 { // 子串中已经满足要求，缩小子串范围
			if tmp > i-left+1 {
				tmp = i - left + 1
				ans = s[left : i+1]
			}
			if _, ok := mp[s[left]]; ok { // 字符有效
				mp[s[left]] += 1
				if mp[s[left]] == 1 { // 符合要求
					cnt += 1
				}
			}
			left += 1
		}
	}

	return ans
}

func main() {
	testCases := []struct {
		s string
		t string
	}{
		{"ADOBECODEBANC", "ABC"},
		{"a", "a"},
		{"a", "aa"},
	}

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

632. 最小区间

题面

你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

示例 1：

输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]

输出：[20,24]

解释：

列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。

列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。

列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

示例 2：

输入：nums = [[1,2,3],[1,2,3],[1,2,3]]

输出：[1,1]

提示：

nums.length == k

1 <= k <= 3500

1 <= nums[i].length <= 50

-105 <= nums[i][j] <= 10^5

nums[i] 按非递减顺序排列

思路说明

构建pair，包含数字和位置，然后排序，构建一个滑动窗口，窗口包含所有index并且窗口最小

题解

// 632.最小区间
package main

import (
	"fmt"
	"slices"
)

func smallestRange(nums [][]int) []int {
	type pair struct{ x, i int } // 数字和他们所在的位置
	pairs := []pair{}

	for i, arr := range nums {
		for _, num := range arr {
			pairs = append(pairs, pair{num, i})
		}
	}

	slices.SortFunc(pairs, func(a, b pair) int { return a.x - b.x })

	ansL, ansR := pairs[0].x, pairs[len(pairs)-1].x
	mp := make(map[int]int)
	left := 0

	for _, p := range pairs {
		r, i := p.x, p.i
		mp[i] += 1

		for len(mp) == len(nums) { // 每个列表都至少包含一个数
			l, i := pairs[left].x, pairs[left].i
			if r-l < ansR-ansL {
				ansL, ansR = l, r
			}
			mp[i] -= 1
			if mp[i] == 0 {
				delete(mp, i)
			}
			left += 1
		}
	}
	return []int{ansL, ansR}
}

func main() {
	testCases := [][][]int{
		[][]int{
			[]int{4, 10, 15, 24, 26},
			[]int{0, 9, 12, 20},
			[]int{5, 18, 22, 30},
		},
		[][]int{
			[]int{1, 2, 3},
			[]int{1, 2, 3},
			[]int{1, 2, 3},
		},
	}

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