leetcode-灵神跟练-滑动窗口与双指针-不定长滑动窗口-越长越合法+求最短+最小
定长滑动窗口-越长越合法/求最短/最小
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 个美丽子字符串：
- 子字符串 “100011001” 。
- 子字符串 “100011001” 。
- 子字符串 “100011001” 。
- 子字符串 “100011001” 。
- 子字符串 “100011001” 。
- 子字符串 “100011001” 。
- 子字符串 “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))
}
}