滑动窗口算法精解：用C++高效解决子串/子数组问题

滑动窗口算法精解：用C++高效解决子串/子数组问题

引用

CSDN

1.

https://m.blog.csdn.net/muzibuku/article/details/146169125

滑动窗口算法是一种高效处理连续子序列问题的算法，通过维护一个动态变化的窗口区间，将暴力算法的O(n²)时间复杂度优化到O(n)。本文将从滑动窗口算法的基本概念出发，通过多个经典应用场景的代码实现，深入解析其核心思想和适用场景。

一、滑动窗口的本质：智能伸缩的取景框

滑动窗口算法如同一个智能摄像机，在数据序列中寻找最完美的"镜头"。它通过维护一个动态变化的窗口区间，将暴力算法的O(n²)时间复杂度优化到O(n)，特别适用于解决连续子序列相关问题。我们将从三大经典应用场景深入解析：

二、滑动窗口的三大核心要素

2.1 窗口维护三要素

int slidingWindowTemplate(vector<int>& nums, int k) {
    int left = 0, right = 0;    // 双指针定义窗口边界
    unordered_map<int, int> window; // 窗口状态记录
    int valid = 0;              // 满足条件的指标
    
    while (right < nums.size()) {
        // 1. 扩展右边界
        int c = nums[right++];  
        window[c]++;
        if (window[c] == k) valid++;
        
        // 2. 收缩左边界条件
        while (valid == target) { 
            // 3. 更新最优解
            res = min(res, right - left);
            
            int d = nums[left++];
            if (window[d] == k) valid--;
            window[d]--;
        }
    }
    return res;
}

2.2 算法复杂度分析

三、基础应用：最长无重复子串（LeetCode 3）

3.1 哈希表+双指针实现

int lengthOfLongestSubstring(string s) {
    vector<int> map(128, -1);  // ASCII直接寻址
    int maxLen = 0, left = 0;
    
    for (int right = 0; right < s.size(); ++right) {
        if (map[s[right]] >= left) 
            left = map[s[right]] + 1;  // 跳跃收缩
        
        map[s[right]] = right;         // 记录最新位置
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}
// 输入："abcabcbb" → 输出：3（"abc"）

算法亮点：

• ASCII直接映射：O(1)时间查询
• 左边界跳跃：避免逐次收缩
• 实时更新最大值：无需额外存储

四、进阶应用：最小覆盖子串（LeetCode 76）

4.1 多条件窗口维护

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, start = 0, len = INT_MAX;
    
    while (right < s.size()) {
        char c = s[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++];
            if (need.count(d)) {
                if (window[d] == need[d]) valid--;
                window[d]--;
            }
        }
    }
    return len == INT_MAX ? "" : s.substr(start, len);
}
// 输入：s = "ADOBECODEBANC", t = "ABC" → 输出："BANC"

关键技巧：

• 需求字典(need)：记录目标字符频次
• 有效计数(valid)：跟踪匹配字符数
• 动态记录最优解：实时更新最小窗口

五、滑动窗口的四大变种

5.1 固定窗口大小

vector<double> findAverages(vector<int>& arr, int k) {
    vector<double> res;
    int sum = 0;
    for (int right = 0; right < arr.size(); ++right) {
        sum += arr[right];
        if (right >= k-1) {
            res.push_back(sum / (double)k);
            sum -= arr[right - k + 1];
        }
    }
    return res;
}
// 输入：[1,3,2,6,-1], k=3 → 输出：[2.0, 3.67, 2.33]

5.2 最多K次替换后的最长子串

int characterReplacement(string s, int k) {
    vector<int> count(26);
    int maxCount = 0, maxLen = 0;
    int left = 0;
    
    for (int right = 0; right < s.size(); ++right) {
        maxCount = max(maxCount, ++count[s[right]-'A']);
        while (right-left+1 - maxCount > k) {
            count[s[left++]-'A']--;
        }
        maxLen = max(maxLen, right-left+1);
    }
    return maxLen;
}
// 输入：s="AABABBA", k=1 → 输出：4（"AABA"→"AAAA"）

六、性能优化与陷阱规避

6.1 常见性能陷阱

6.2 高级优化技巧

// 优化点1：数组替代哈希表
vector<int> count(128, 0); // 处理ASCII字符
// 优化点2：跳跃收缩左边界
left = max(left, lastPos + 1);
// 优化点3：提前终止循环
if (maxLen == s.size()) break;

七、滑动窗口的六大应用场景

1. 子串搜索：最小覆盖子串、字母异位词
2. 数组统计：最大平均值、乘积小于K
3. 流式处理：数据流中位数、最近K元素
4. 字符串分析：重复DNA序列、回文子串
5. 时间序列：股票最佳时机、日程安排
6. 资源分配：课程安排、任务调度

结语：滑动窗口的智慧之光

滑动窗口算法展现了算法设计的三个核心哲学：

1. 时空权衡：用空间记录状态换取时间效率
2. 增量思维：避免重复计算已有信息
3. 最优剪枝：及时排除无效解可能

当你在LeetCode遇到以下题目时，滑动窗口将是你的破题利器：

• 209. 长度最小的子数组
• 424. 替换后的最长重复字符
• 567. 字符串的排列

掌握滑动窗口的精髓，你将能优雅地解决大量子序列问题，如同拥有解开数据迷宫的万能钥匙。记住：优秀的算法不是魔法，而是对问题模式的深刻洞察与巧妙建模。