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 個美麗子字串：
- 子字串 “1011” 。
- 子字串 “1011” 。
- 子字串 “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))
}
}