滑动窗口
滑动窗口（Sliding Window） 是一种常见的算法技巧，主要用于在数组或字符串上寻找满足某种条件的子区间（window），其核心思路是：
- 定义窗口左右边界：用两个指针
left、right表示当前窗口的起始和结束位置。 - 维护窗口中的状态：随着
right向右移动，将新元素纳入窗口；当窗口不再满足条件时，就移动left将元素移出窗口。 - 边动边更新答案：在每次移动之后，根据窗口当前状态更新最优解（如最大和、最长长度等）。
这种技巧的优势在于，整个数组／字符串只需遍历一次，时间复杂度通常为 O(n)。
以下分别给出两个典型例子，并用 Go 和 PHP 展示实现。
1. 固定大小窗口 —— 求长度为 k 的子数组最大和
main.go
package main
import (
"fmt"
)
// maxSubarraySumFixedWindow 计算数组中所有长度为 k 的子数组的最大和
func maxSubarraySumFixedWindow(nums []int, k int) int {
n := len(nums)
if n < k || k <= 0 {
return 0
}
// 先计算第一个窗口的和
sum := 0
for i := 0; i < k; i++ {
sum += nums[i]
}
maxSum := sum
// 滑动窗口：右边界从 k 开始，左边界 i-k
for i := k; i < n; i++ {
sum += nums[i] // 窗口右端新增 nums[i]
sum -= nums[i-k] // 窗口左端移除 nums[i-k]
if sum > maxSum {
maxSum = sum
}
}
return maxSum
}
func main() {
arr := []int{1, -2, 3, 4, -1, 2, 1}
k := 3
fmt.Printf("数组 %v 中，长度为 %d 的子数组最大和为 %d\n",
arr, k, maxSubarraySumFixedWindow(arr, k))
}
/**
运行示例：
$ go run main.go
数组 [1 -2 3 4 -1 2 1] 中，长度为 3 的子数组最大和为 7
*/main.php
<?php
/**
* 计算数组中所有长度为 $k 的子数组的最大和
*
* @param array $nums 输入整数数组
* @param int $k 窗口大小
* @return int 最大子数组和
*/
function maxSubarraySumFixedWindow(array $nums, int $k): int {
$n = count($nums);
if ($n < $k || $k <= 0) {
return 0;
}
// 先计算第一个窗口的和
$sum = array_sum(array_slice($nums, 0, $k));
$maxSum = $sum;
// 滑动窗口：右边界从 k 开始，左边界 i-k
for ($i = $k; $i < $n; $i++) {
$sum += $nums[$i];
$sum -= $nums[$i - $k];
if ($sum > $maxSum) {
$maxSum = $sum;
}
}
return $maxSum;
}
// 测试
$arr = [1, -2, 3, 4, -1, 2, 1];
$k = 3;
echo "数组 [" . implode(', ', $arr) . "] 中，长度为 $k 的子数组最大和为 " .
maxSubarraySumFixedWindow($arr, $k) . PHP_EOL;2. 动态窗口 —— 求最长不含重复字符的子串
main.go
package main
import "fmt"
// lengthOfLongestSubstring 求字符串中最长不含重复字符的子串长度
func lengthOfLongestSubstring(s string) int {
lastIndex := make(map[rune]int)
maxLen := 0
left := 0
for right, ch := range s {
// 如果字符在窗口内出现过，就把左指针移动到上一次出现位置的下一位
if idx, ok := lastIndex[ch]; ok && idx >= left {
left = idx + 1
}
lastIndex[ch] = right
currLen := right - left + 1
if currLen > maxLen {
maxLen = currLen
}
}
return maxLen
}
func main() {
str := "abcabcbb"
fmt.Printf("字符串 \"%s\" 的最长不含重复字符子串长度为 %d\n",
str, lengthOfLongestSubstring(str))
}
/**
运行结果：
$ go run main.go
字符串 "abcabcbb" 的最长不含重复字符子串长度为 3
*/main.php
<?php
/**
* 求字符串中最长不含重复字符的子串长度
*
* @param string $s 输入字符串
* @return int 最长子串长度
*/
function lengthOfLongestSubstring(string $s): int {
$lastIndex = [];
$maxLen = 0;
$left = 0;
$chars = preg_split('//u', $s, -1, PREG_SPLIT_NO_EMPTY);
foreach ($chars as $right => $ch) {
if (isset($lastIndex[$ch]) && $lastIndex[$ch] >= $left) {
$left = $lastIndex[$ch] + 1;
}
$lastIndex[$ch] = $right;
$currLen = $right - $left + 1;
if ($currLen > $maxLen) {
$maxLen = $currLen;
}
}
return $maxLen;
}
// 测试
$str = "abcabcbb";
echo "字符串 \"$str\" 的最长不含重复字符子串长度为 " .
lengthOfLongestSubstring($str) . PHP_EOL;通过以上示例，你可以看到滑动窗口既可用于「固定长度」的场景，也可支持「动态变化」的场景；核心都是左右指针维护窗口区间，并在每次移动时更新状态和最优解。
