当前位置：首页 > news >正文

【面试HOT200】滑动窗口篇

news 来源：原创 2024/5/19 6:45:39

系列综述：
💞目的：本系列是个人整理为了秋招面试的，整理期间苛求每个知识点，平衡理解简易度与深入程度。
🥰来源：材料主要源于【CodeTopHot200】进行的，每个知识点的修正和深入主要参考各平台大佬的文章，其中也可能含有少量的个人实验自证。
🤭结语：如果有帮到你的地方，就点个赞和关注一下呗，谢谢🎈🎄🌷！！！
🌈【C++】秋招&实习面经汇总篇

文章目录

- - 基础知识
  - - 概述
  - 算法例题
  - - 3. 无重复字符的最长子串
    - 239. 滑动窗口最大值
    - 76. 最小覆盖子串
    - 438. 找到字符串中所有字母异位词
- 参考博客

😊点此到文末惊喜↩︎

基础知识

概述

作用
- 求解线性表（数组/字符串）中，满足条件的连续子区间性质（最长/最短等）的相关问题
- 通过复用子区间性质的计算结果，从而减少循环层数，降低时间复杂度
原理
- 当不满足条件的时候扩大窗口，当满足条件之后减小窗口
- 将条件进行使用bool函数封装，构建基本算法框架
核心：按照条件进行滑动和计算符合条件的窗口性质
基本框架

解决的问题：
给定一个线性表（字符串、数组等），一次遍历求满足指定条件的连续子部分

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {// 参数的健壮性检查if (s.size() < t.size()) return ;// 子区间性质的信息缓存unordered_map<char, int> need, window;for (char c : t) need[c]++;int valid = 0; // 算法int left = 0, right = 0;while (right < s.size()) {// c 是将移入窗口的字符char c = s[right];// 右移窗口right++;// 进行窗口内数据的一系列更新.../*** debug 输出的位置 ***/printf("window: [%d, %d)\n", left, right);/********************/// 判断左侧窗口是否要收缩while (window needs shrink) {// d 是将移出窗口的字符char d = s[left];// 左移窗口left++;// 进行窗口内数据的一系列更新...}}
}

算法例题

3. 无重复字符的最长子串

问题
- 给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
思路
- 滑动窗口

int Template(string s) {// 健壮性检查if(s.size() == 0) return 0;// TODO：记录窗口子区间性质int max_len = 0;unordered_set<char> windows;// 初始化int left = 0, right = 0;while (right < s.size()) {// 缩小窗口while (windows.count(s[right]) != 0){windows.erase(s[left]);++left;}  // 增大窗口windows.insert(s[right]);++right;max_len = max(max_len, right-left); // TODO：更新子区间性质}return max_len;
}

239. 滑动窗口最大值

题目

class Solution {
private:class MyQueue { //单调队列（从大到小）public:deque<int> que; // 使用deque来实现单调队列// 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。// 同时pop之前判断队列当前是否为空。void pop (int value) {if (!que.empty() && value == que.front()) {que.pop_front();}}// 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。 // 这样就保持了队列里的数值是单调从大到小的了。void push (int value) {while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。int front() {return que.front();}};
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue que;vector<int> result;for (int i = 0; i < k; i++) { // 先将前k的元素放进队列que.push(nums[i]);}result.push_back(que.front()); // result 记录前k的元素的最大值for (int i = k; i < nums.size(); i++) {que.pop(nums[i - k]); // 滑动窗口移除最前面元素que.push(nums[i]); // 滑动窗口前加入最后面的元素result.push_back(que.front()); // 记录对应的最大值}return result;}
};

76. 最小覆盖子串

题目
- 返回字符串 s 中包含字符串 t 的全部字符的最小窗口
思路
- 不断滑动增加窗口，当窗口满足条件时开始收缩并记录窗口的起始位置和长度

string SlideWindow(string s, string t) {// 窗口性质：need记录子串情况，window记录合适窗口unordered_map<char, int> need, window;	// need记录目标窗口状态，window记录当前窗口状态for (char c : t) need[c]++;		// 子串中可能出现重复字母int valid = 0;	// 目标窗口和当前窗口符合字符的大小int start = 0, len = INT_MAX;	// 符合条件子串的起始位置和长度// 初始化及滑动窗口算法int left = 0, right = 0;while (right < s.size()) {char c = s[right];	// c 是将移入窗口的字符right++;			// 右移窗口// 进行窗口内数据的一系列更新if (need.count(c)) {window[c]++;if (window[c] == need[c])valid++;}while (valid == need.size()) {	// TODO：收缩条件// TODO：更新结果记录if (right - left < len) {	start = left;// 更新起始值len = right - left;// 最小长度}// 收缩窗口char d = s[left];left++;// TODO：收缩处理if (need.count(d)) {if (window[d] == need[d])valid--;window[d]--;}                    }}// 返回最小覆盖子串return len == INT_MAX ?"" : s.substr(start, len);
}

438. 找到字符串中所有字母异位词

问题
- 给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。
- 异位词指由相同字母重排列形成的字符串（包括相同的字符串）。
思路
- 快慢指针 + 交换

// 返回字符串 s 中包含字符串 t 的全部字符的最小窗口
string SlideWindow(string s, string t) {// need记录子串情况，window记录合适窗口unordered_map<char, int> need, window;for (char c : t) need[c]++;int left = 0, right = 0;// 记录最小覆盖子串的起始索引及长度int start = 0, len = INT_MAX;int valid = 0;while (right < s.size()) {char c = s[right];	// c 是将移入窗口的字符right++;			// 右移窗口// 进行窗口内数据的一系列更新if (need.count(c)) {window[c]++;if (window[c] == need[c])valid++;}while (valid == need.size()) {	// TODO：收缩条件// TODO：更新结果记录if (right - left < len) {	start = left;// 更新起始值len = right - left;// 最小长度}// 收缩窗口char d = s[left];left++;// TODO：收缩处理if (need.count(d)) {if (window[d] == need[d])valid--;window[d]--;}                    }}// 返回最小覆盖子串return len == INT_MAX ?"" : s.substr(start, len);
}