滑动窗口

滑动窗口算法是一种用于解决数组/字符串问题的技巧，特别适用于求解子数组/子字符串的问题，比如最长无重复字符的子字符串、有 K 个最大元素的子数组等问题。滑动窗口可以帮助我们在 O(N)的时间复杂度内解决这类问题。

滑动窗口算法的通用思路如下：

确定窗口的边界：窗口通常由两个指针定义，一个表示窗口的开始，另一个表示窗口的结束。
移动窗口的结束指针：增大窗口，直到窗口内的子数组/子字符串满足题目要求。
移动窗口的开始指针：在保持窗口内子数组/子字符串满足题目要求的前提下，缩小窗口以寻找更小的满足条件的窗口。
在移动窗口的过程中，根据题目要求计算所需的值。
记录所需的最优解。

下面是一个使用 Go 语言实现的滑动窗口算法的例子，该例子解决的是找出字符串中最长无重复字符的子字符串的长度：

package main

import (
	"fmt"
)

func lengthOfLongestSubstring(s string) int {
	charIndexMap := make(map[byte]int)
	maxLength := 0
	start := 0 // 窗口开始位置

	for end := 0; end < len(s); end++ {
		if index, ok := charIndexMap[s[end]]; ok && index >= start {
			// 如果字符已经在窗口中，移动窗口的开始位置
			start = index + 1
		}
		// 更新字符的最新位置
		charIndexMap[s[end]] = end
		// 更新最长无重复字符的子字符串的长度
		if end-start+1 > maxLength {
			maxLength = end - start + 1
		}
	}

	return maxLength
}

func main() {
	fmt.Println(lengthOfLongestSubstring("abcabcbb")) // 输出: 3
}

在这个例子中，我们使用了一个哈希表charIndexMap来记录字符最后一次出现的位置。我们的窗口由start和end两个指针定义，分别表示窗口的开始和结束位置。我们遍历字符串，不断移动end指针来扩大窗口。如果遇到一个已经在窗口中的字符，我们就更新start指针来缩小窗口。在每一步中，我们都检查并更新最长无重复字符子字符串的长度。

滑动窗口算法的关键在于如何根据问题的需求来合理地移动窗口的两个指针，并在过程中维护和更新必要的数据结构和变量。

hot-100

滑动窗口