Golang 滑动窗口模板与套路详解
针对 LeetCode 1004（最大连续1的个数 III）这类问题，以下是专门为 Golang 开发者准备的滑动窗口实现模板、适用场景和常见变种：
Golang 滑动窗口模板（1004 类型）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| func longestOnes(nums []int, k int) int {
left, maxLen, zeroCount := 0, 0, 0
for right := 0; right < len(nums); right++ {
if nums[right] == 0 {
zeroCount++
}
for zeroCount > k {
if nums[left] == 0 {
zeroCount--
}
left++
}
if windowSize := right - left + 1; windowSize > maxLen {
maxLen = windowSize
}
}
return maxLen
}
|
核心套路与技巧（Golang 实现）
双指针初始化：
1
2
3
| left := 0
maxLen := 0
counter := 0
|
右指针移动逻辑：
1
2
3
4
5
| for right := 0; right < len(nums); right++ {
if condition(nums[right]) {
counter++
}
|
窗口收缩条件：
1
2
3
4
5
6
| for counter > k {
if condition(nums[left]) {
counter--
}
left++
}
|
结果更新：
1
2
3
| if windowSize := right - left + 1; windowSize > maxLen {
maxLen = windowSize
}
|
Golang 常见变种实现
1. 替换后的最长重复字符（LeetCode 424）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| func characterReplacement(s string, k int) int {
count := make([]int, 26)
left, maxCount, maxLen := 0, 0, 0
for right, ch := range s {
count[ch-'A']++
if count[ch-'A'] > maxCount {
maxCount = count[ch-'A']
}
if (right-left+1)-maxCount > k {
count[s[left]-'A']--
left++
}
if windowSize := right-left+1; windowSize > maxLen {
maxLen = windowSize
}
}
return maxLen
}
|
2. 水果成篮（LeetCode 904）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| func totalFruit(fruits []int) int {
basket := make(map[int]int)
left, maxFruits := 0, 0
for right, fruit := range fruits {
basket[fruit]++
for len(basket) > 2 {
basket[fruits[left]]--
if basket[fruits[left]] == 0 {
delete(basket, fruits[left])
}
left++
}
if windowSize := right-left+1; windowSize > maxFruits {
maxFruits = windowSize
}
}
return maxFruits
}
|
3. 最小覆盖子串（LeetCode 76）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| func minWindow(s string, t string) string {
need := make(map[byte]int)
window := make(map[byte]int)
for i := range t {
need[t[i]]++
}
left, valid := 0, 0
start, length := 0, math.MaxInt32
for right := 0; right < len(s); right++ {
c := s[right]
if _, exists := need[c]; exists {
window[c]++
if window[c] == need[c] {
valid++
}
}
for valid == len(need) {
if right-left+1 < length {
start = left
length = right - left + 1
}
d := s[left]
if _, exists := need[d]; exists {
if window[d] == need[d] {
valid--
}
window[d]--
}
left++
}
}
if length == math.MaxInt32 {
return ""
}
return s[start : start+length]
}
|
滑动窗口适用场景总结
| 问题特征 | 示例题目 | Golang 实现要点 |
|---|
| 有限修改连续序列 | 1004, 424, 2024 | 使用计数器跟踪修改需求 |
| 不同元素数量限制 | 904, 340 | 使用 map 跟踪元素种类 |
| 最短满足条件子串 | 209, 76 | 收缩时更新最小值 |
| 固定窗口大小 | 643, 1343 | 维护固定大小的窗口 |
| 无重复字符 | 3, 159 | 使用 map 或 set 检测重复 |
Golang 实现技巧
计数器选择：
- 简单计数：
int 变量 - 字符频率：
[26]int 或 [128]int - 通用元素：
map[type]int
边界处理：
1
2
3
4
|
if len(nums) == 0 {
return 0
}
|
性能优化：
- 避免不必要的内存分配（预分配 map 大小）
- 使用数组代替 map 当键范围有限时
- 减少循环内部的计算
复杂条件处理：
1
2
3
4
|
for !isValid(window, condition) {
}
|
掌握这些 Golang 实现的滑动窗口模式和变种，能高效解决 LeetCode 上大部分滑动窗口问题。关键是根据问题特征选择合适的计数器类型和窗口收缩条件。
