什么是滑动窗口

滑动窗口算法是一种常用的算法，用于在线性数据结构（如数组或链表）中寻找特定模式的子串或子序列。它的基本思想是维护一个固定大小的窗口，并在每次移动窗口时更新窗口内的状态，以便有效地查找目标模式。

滑动窗口算法通常包含两个指针，一个指向窗口的起始位置，一个指向窗口的结束位置。初始时，这两个指针都指向数据结构的第一个元素。然后，我们将窗口向右移动，更新窗口内的状态，并检查是否已找到目标模式。如果找到了目标模式，我们记录结果，并继续向右移动窗口以查找其他可能的匹配。如果没有找到目标模式，则继续向右移动窗口，重复以上步骤。

滑动窗口算法通常用于解决字符串或数组相关的问题，如最小子串问题，最大子数组问题，子字符串排列问题等。它的时间复杂度通常为O(n)，其中n是数据结构中元素的数量。

C++实现

cpp
#include <iostream>
#include <vector>

using namespace std;

class SlidingWindow {
private:
    vector<int> arr;
    int k;
    int window_start;
    int window_sum;
public:
    SlidingWindow(vector<int> input, int k) {
        this->arr = input;
        this->k = k;
        this->window_start = 0;
        this->window_sum = 0;
        for (int i = 0; i < k; i++) {
            this->window_sum += arr[i];
        }
    }

    void move_window() {
        this->window_sum -= arr[window_start];
        this->window_start++;
        this->window_sum += arr[window_start + k - 1];
    }

    int get_max_sum() {
        int max_sum = window_sum;
        for (int i = window_start + k; i < arr.size(); i++) {
            move_window();
            max_sum = max(max_sum, window_sum);
        }
        return max_sum;
    }
};

int main() {
    vector<int> arr = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    SlidingWindow sliding_window(arr, k);
    int max_sum = sliding_window.get_max_sum();
    cout << "Max sum of each " << k << " sized subarray: " << max_sum << endl;
    return 0;
}