定长滑动窗口

核心思想

03xf文章：【套路】教你解决定长滑窗！适用于所有定长滑窗题目！

维护一个大小不变的“框”，在数据序列上平移，通过“入窗”和“出窗”的增量更新来避免重复计算。

定长滑动窗口核心思想.drawio.svg

为什么要用它？

假设数组长度为 $N$ ，窗口大小为 $K$ ，求窗口内元素和的最大值：

特性	暴力枚举	滑动窗口
计算逻辑	每次重新计算窗口内 $K$ 个元素的和	结果 = 上一轮结果 + 新入 - 旧出
时间复杂度	$O (N \times K)$	$O (N)$
重复计算	中间 $K - 2$ 个元素被重复访问	每个元素仅进、出一次

模板

假设数组长度为 $N$ ，窗口大小为 $K$ ，求窗口内元素和的最大值

模板一：先计算第一个窗口，再从索引 $k$ 开始遍历到末尾

模板二：直接一次遍历，每次判断窗口长度

维度	模板一 (分步)	模板二 (一次遍历)
推荐度	首选	备选
适用场景	基础求和、求平均值、维护简单计数	逻辑极其简单或追求极短代码量时
调试难度	低（边界清晰：`0` 到 `k-1`，然后 `k` 到 `n`）	中（容易在 `i >= k-1` 还是 `i >= k` 上纠结）
扩展性	强（容易插入复杂的初始化逻辑）	一般（所有逻辑塞在一个 `if` 里）

Cpp

模板一：先计算第一个窗口，再从索引 $k$ 开始遍历到末尾

long long slidingWindow(vector<int>& nums, int k) {
    int n = nums.size();
    if (n < k) return 0;

    // 1. 初始化阶段：手动计算第一个长度为 k 的窗口和
    // 使用 0LL 确保累加过程在 long long 精度下进行，防止溢出
    long long current_window_sum = accumulate(nums.begin(), nums.begin() + k, 0LL);
    long long max_res = current_window_sum;

    // 2. 滑动阶段：i 指向当前待“入窗”的新元素
    for (int i = k; i < n; ++i) {
        // 核心动作：加上新进来的 nums[i]，减去过期的 nums[i - k]
        current_window_sum += nums[i] - nums[i - k];
        
        // 3. 更新全局最大值
        max_res = max(max_res, current_window_sum);
    }

    return max_res;
}

模板二：直接一次遍历，每次判断窗口长度

long long slidingWindow(vector<int>& nums, int k) {
    int n = nums.size();
    long long current_sum = 0;
    // 使用 long long 的最小值作为初始对比值
    long long res = LLONG_MIN;

    for (int i = 0; i < n; ++i) {
        // 1. 进：无论窗口是否填满，先累加当前元素
        current_sum += nums[i];

        // 2. 算：当索引 i 增长到 k-1 时，窗口正式填满（包含 k 个元素）
        if (i >= k - 1) {
            // 此时窗口内的元素区间是 [i - k + 1, i]
            res = max(res, current_sum);
            
            // 3. 出：在记录完结果后，减去窗口最左侧元素，为下一轮滑动腾位
            // 这里 i - (k - 1) 是窗口的最左端索引
            current_sum -= nums[i - (k - 1)];
        }
    }
    return res;
}

Python

模板一：先计算第一个窗口，再从索引 $k$ 开始遍历到末尾

def slidingWindow(nums, k):
# 1. 初始化阶段：计算第一个窗口的结果
current_window_sum = sum(nums[:k])
max_res = current_window_sum

# 2. 滑动阶段：从索引 k 开始遍历到数组末尾
for i in range(k, len(nums)):
    # 进入：当前元素 nums[i]
    # 离开：窗口最左边的元素 nums[i - k]
    current_window_sum += nums[i] - nums[i - k]
    
    # 3. 更新全局最优解
    max_res = max(max_res, current_window_sum)
    
return max_res

模板二：直接一次遍历，每次判断窗口长度

def slidingWindow(nums, k):
    current_sum = 0
    res = -float('inf')
    
    for i in range(len(nums)):
        # 进：无论如何都先把元素加进来
        current_sum += nums[i]
        
        # 当窗口长度达到 k 时，开始记录结果并移除左侧元素
        if i >= k - 1:
            res = max(res, current_sum)
            # 出：移除即将出界的左端元素
            current_sum -= nums[i - (k - 1)]
            
    return res

题目精讲

题目一：

来源：力扣1456. 定长子串中元音的最大数目

给你字符串 s 和整数 k 。

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的 元音字母 为（a, e, i, o, u）。

思路

套模板即可，注意窗口右端点在 $i$ 时，由于窗口长度为 $k$ ，所以窗口左端点为 $i - k + 1$

推荐使用模板一，养成习惯

代码实现

Python模板一

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        # val = "aeiou"
        val = {"a", "e", "i", "o", "u"}
        ans = cur = sum(1 if c in val else 0 for c in s[:k])

        for i in range(k, len(s)):
            if s[i] in val:
                cur += 1
            if s[i - k] in val:
                cur -= 1
            ans = max(ans, cur)
            if ans == k:
                return k

        return ans

Python模板二

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        # val = "aeiou"
        val = {"a", "e", "i", "o", "u"}
        ans = cur = 0 

        for i, char in enumerate(s):
            if char in val:
                cur += 1
            if i >= k:
                if s[i - k] in val:
                    cur -= 1

            ans = max(ans, cur)
            if ans == k:
                return k

        return ans

题目二

来源：力扣1297. 子串的最大出现次数

给你一个字符串 s ，请你返回满足以下条件且出现次数最大的任意子串的出现次数：

子串中不同字母的数目必须小于等于 maxLetters 。

子串的长度必须大于等于 minSize 且小于等于 maxSize 。

思路

由于子串长度越小，子串中不同字母的数目越小，越能满足 $<= ma xL e tt ers$ 的条件；

子串越短，子串在 $s$ 中出现的次数越多；

结合上面两个性质，我们只需考虑长度恰好等于 $min S i ze$ 的子串（ $ma x S i ze$ 是多余的）。

可以使用哈希表高效统计不同字母的数目和子串出现次数

当字母进入窗口时，增加字母的出现次数。如果增加之前，这个字母的出现次数等于 0，那么不同字母的数目加一。
当字母离开窗口时，减少字母的出现次数。如果减少之后，这个字母的出现次数等于 0，那么不同字母的数目减一。

代码实现

Python模板一

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        s_cnt = defaultdict(int)
        c_cnt = defaultdict(int)

        for i in range(minSize):
            c_cnt[s[i]] += 1

        if len(c_cnt) <= maxLetters:
            s_cnt[s[:minSize]] += 1

        for i in range(minSize, len(s)):
            c_cnt[s[i]] += 1
            c_cnt[s[i - minSize]] -= 1
            if c_cnt[s[i - minSize]] == 0:
                del c_cnt[s[i - minSize]]

            if len(c_cnt) <= maxLetters:
                s_cnt[s[i - minSize + 1 : i + 1]] += 1

        return max(s_cnt.values(), default=0)