C++ 滑动窗口算法模板

1. 固定窗口大小

int fixedSlidingWindow(vector<int>& nums, int k) 
{
    int n = nums.size();
    int sum = 0;
    
    // 计算初始窗口
    for (int i = 0; i < k; i++) 
    {
        sum += nums[i];
    }
    
    int maxSum = sum;
    
    // 滑动窗口
    for (int i = k; i < n; i++) 
    {
        sum += nums[i] - nums[i - k];  // 加新元素，减旧元素
        maxSum = max(maxSum, sum);
    }
    
    return maxSum;
}

2. 可变窗口大小（求最大窗口）

3.无重复字符的最长子串

class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        int n = s.size();

        unordered_set<int> hash_set;

        int ans = 0;
        int left = 0;
        for(int right = 0; right < n; ++right)
        {
            char c = s[right];

            while(hash_set.count(c))
            {
                hash_set.erase(s[left++]);
            }

            hash_set.insert(c);

            ans = max(ans, right - left + 1);
        }

        return ans;
    }
};

3. 可变窗口大小（求最小窗口）

76.最小覆盖子串

class Solution {
public:
    string minWindow(string s, string t) 
    {
        int m = s.size();
        int n = t.size();

        // 如果 s 比 t 短, 直接返回空字符串 
        if(m < n) return "";

        // 统计 t 中每个字符出现的次数
        unordered_map<char, int> t_map;
        for(auto& ch : t)
        {
            t_map[ch]++;
        }

        // 用于统计当前窗口中字符的出现次数
        unordered_map<char, int> s_map;
        // 滑动窗口的左右边界
        int left = 0, right = 0;
        // 记录最小窗口的起始位置和长度
        int ans_left = 0, min_len = INT_MAX;
        // 统计当前窗口中满足 t 要求的字符数量
        int cnt = 0;

        while(right < m)
        {
            // 拓展右边界直到满足条件 cnt == t_map.size();
            if(t_map.count(s[right]))
            {
                s_map[s[right]]++;
                // 如果该字符在窗口中的数量刚好达到 t 中的要求，增加 cnt
                if(s_map[s[right]] == t_map[s[right]]) cnt++;
            }

            // 右边界右移
            right++;

            // 有边界满足条件时，缩短左边界
            while(cnt == t_map.size())
            {
                // 当窗口小于 min_len 时, 更新答案
                if(min_len > right - left)
                {
                    ans_left = left;
                    min_len = right - left;
                }

                if(t_map.count(s[left]))
                {
                    s_map[s[left]]--;
                    // 如果该字符的数量不再满足t中的要求，减少 cnt
                    if(s_map[s[left]] < t_map[s[left]]) cnt--;
                }

                // 左边界右移
                left++;
            }
        }

        // 如果找到了最小窗口，返回对应的子串，否则返回空字符串
        return min_len == INT_MAX ? "" : s.substr(ans_left, min_len); 
    }   
};

使用场景

滑动窗口算法通常用于解决以下类型的问题：

• 子串/子数组问题（如最小覆盖子串、最长无重复子串）
• 固定大小的子数组问题（如大小为k的子数组的最大和）
• 满足特定条件的连续子序列问题

复杂度分析

滑动窗口算法通常的时间复杂度为O(n)，空间复杂度为O(k)，其中k是字符集或元素集的大小。