编辑
2023-03-06
学习
00
请注意,本文编写于 637 天前,最后修改于 304 天前,其中某些信息可能已经过时。

目录

什么是滑动窗口
C++实现

image.png

什么是滑动窗口

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

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

滑动窗口算法通常用于解决字符串或数组相关的问题,如最小子串问题,最大子数组问题,子字符串排列问题等。它的时间复杂度通常为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; }

本文作者:beiklive

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!