C++ 滑动窗口算法模板

滑动窗口是一种常用的算法技巧，主要用于解决数组/字符串的子区间问题。以下是 C++ 中滑动窗口的通用模板：

基本模板

int slidingWindowTemplate(vector<int>& nums, int k) 
{
    int n = nums.size();
    int left = 0, right = 0;  // 窗口左右边界
    int result = 0;           // 存储结果
    unordered_map<int, int> window; // 用于记录窗口内元素的状态
    
    while (right < n) 
    {
        // 扩大窗口，加入右边元素
        int c = nums[right];
        right++;
        window[c]++;  // 更新窗口状态
        
        // 判断是否需要收缩窗口
        while (window needs shrink) 
        {  // 这里需要根据具体问题实现条件
            // 缩小窗口，移除左边元素
            int d = nums[left];
            left++;
            window[d]--;  // 更新窗口状态
        }
        
        // 更新结果（根据具体问题可能需要放在不同位置）
        result = max(result, right - left);  // 或其他计算方式
    }
    
    return result;
}

常见变体

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. 可变窗口大小（求最大窗口）

int variableMaxWindow(string s) 
{
    unordered_map<char, int> window;
    int left = 0, right = 0;
    int maxLen = 0;
    
    while (right < s.size()) 
    {
        char c = s[right];
        right++;
        window[c]++;
        
        // 当窗口内有重复字符时，收缩窗口
        while (window[c] > 1) 
        {
            char d = s[left];
            left++;
            window[d]--;
        }
        
        maxLen = max(maxLen, right - left);
    }
    
    return maxLen;
}

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

string minWindow(string s, string t) 
{
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    
    int left = 0, right = 0;
    int valid = 0; // 记录满足条件的字符数
    int start = 0, len = INT_MAX;
    
    while (right < s.size()) {
        char c = s[right];
        right++;
        
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) {
                valid++;
            }
        }
        
        // 当窗口满足条件时，尝试收缩窗口
        while (valid == need.size()) {
            // 更新最小窗口
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            
            char d = s[left];
            left++;
            
            if (need.count(d)) {
                if (window[d] == need[d]) {
                    valid--;
                }
                window[d]--;
            }
        }
    }
    
    return len == INT_MAX ? "" : s.substr(start, len);
}

使用场景

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

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

复杂度分析

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