C++ 滑动窗口算法详解

C++ 滑动窗口算法详解

1. 介绍

滑动窗口算法是一种用于解决数组/字符串子区间问题的优化技术。它通过维护一个窗口（通常是子数组或子字符串），在遍历过程中动态调整窗口的起始和结束位置，从而高效地解决问题。

2. 应用使用场景

• 子数组/子字符串问题：如最大子数组和、最小覆盖子串、最长无重复字符子串等。
• 固定窗口大小问题：如计算固定大小的滑动窗口的平均值。
• 动态窗口大小问题：如满足某些条件的最短或最长子数组。

3. 不同场景下的详细代码实现

场景 1：最大子数组和

问题描述：给定一个整数数组，找到一个具有最大和的连续子数组。

代码实现：

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int maxSubArray(vector<int>& nums) {
    int max_sum = INT_MIN;
    int current_sum = 0;

    for (int num : nums) {
        current_sum = max(num, current_sum + num);
        max_sum = max(max_sum, current_sum);
    }

    return max_sum;
}

int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "最大子数组和: " << maxSubArray(nums) << endl;
    return 0;
}

运行效果：

最大子数组和: 6

场景 2：最小覆盖子串

问题描述：给定一个字符串 s 和一个目标字符串 t，在 s 中找到包含 t 所有字符的最短子串。

代码实现：

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

string minWindow(string s, string t) {
    unordered_map<char, int> target, window;
    for (char c : t) target[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 (target.count(c)) {
            window[c]++;
            if (window[c] == target[c]) valid++;
        }

        while (valid == target.size()) {
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            char d = s[left];
            left++;
            if (target.count(d)) {
                if (window[d] == target[d]) valid--;
                window[d]--;
            }
        }
    }

    return len == INT_MAX ? "" : s.substr(start, len);
}

int main() {
    string s = "ADOBECODEBANC";
    string t = "ABC";
    cout << "最小覆盖子串: " << minWindow(s, t) << endl;
    return 0;
}

运行效果：

最小覆盖子串: BANC

4. 原理解释

• 滑动窗口的核心思想：

  • 维护一个窗口（通常用两个指针表示起始和结束位置）。
  • 通过移动右指针扩展窗口，直到满足条件。
  • 通过移动左指针收缩窗口，优化结果。

• 算法原理：

  • 扩展窗口：右指针向右移动，增加窗口中的元素。
  • 收缩窗口：当窗口满足条件时，左指针向右移动，尝试找到更优解。
  • 更新结果：在每次满足条件时，记录当前窗口的状态。

• 流程图：

  初始化窗口指针 left 和 right
  while right < 数组长度:
      扩展窗口：right++
      更新窗口状态
      while 窗口满足条件:
          更新结果
          收缩窗口：left++
  

5. 测试步骤

1. 编译代码：

   g++ -o sliding_window sliding_window.cpp
   

2. 运行程序：

   ./sliding_window
   

3. 检查输出是否符合预期。

6. 部署场景

• 本地测试：在本地机器上运行程序。
• 算法竞赛：在编程竞赛中使用滑动窗口算法解决问题。
• 生产环境：集成到需要高效处理子数组/子字符串问题的应用中。

7. 材料链接

• LeetCode 滑动窗口问题集
• C++ 官方文档
• 滑动窗口算法详解

8. 总结

滑动窗口算法是解决子数组/子字符串问题的强大工具，能够将时间复杂度从 O(n^2) 优化到 O(n)。通过灵活调整窗口的起始和结束位置，可以高效地解决多种问题。

9. 未来展望

• 扩展到多维数组：研究滑动窗口在多维数组中的应用。
• 结合其他算法：与动态规划、贪心算法等结合，解决更复杂的问题。
• 优化性能：进一步优化滑动窗口的实现，减少空间复杂度。
• 实际应用：在数据流处理、实时分析等领域应用滑动窗口算法。