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

【面试HOT200】滑动窗口篇

article 2024/11/15 10:58:43

系列综述：
💞目的：本系列是个人整理为了秋招面试的，整理期间苛求每个知识点，平衡理解简易度与深入程度。
🥰来源：材料主要源于【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);
}