小龙报个人主页作者简介C研发嵌入式机器人AI等方向学习者❄️个人专栏《优选算法》✨永远相信美好的事情即将发生文章目录前言一、最大的连续1个数1.1题目1.2 算法原理1.2.1 算法思路1.2.2 算法流程1.3 代码二、找到字符串中所有字母的异位词2.1 题目2.2 算法原理2.2.1 算法思路2.2.2 算法流程2.2.2.1 法一2.2.2.2 法二2.3 代码2.3.1 法一代码2.3.2 法二代码总结与每日励前言滑动窗口是算法面试高频考点专门高效求解数组、字符串连续区间类题目能将暴力解法 O (n²) 复杂度优化至线性 O (n)。本文选取两道经典例题可变窗口题型水果成篮、定长窗口题型字母异位词拆解滑动窗口结合哈希表的完整解题流程区分两种窗口处理逻辑附带可直接运行的 C 代码帮读者吃透滑窗通用模板。一、最大的连续1个数1.1题目链接水果成蓝1.2 算法原理核心思想:一段只包含两个数字的最长子串1.2.1 算法思路研究的对象是一段连续的区间可以使用「滑动窗口」思想来解决问题。让滑动窗口满足窗口内水果的种类只有两种。做法右端水果进入窗口的时候用哈希表统计这个水果的频次。这个水果进来后判断哈希表的大小如果大小超过 2说明窗口内水果种类超过了两种。那么就从左侧开始依次将水果划出窗口直到哈希表的大小小于等于 2然后更新结果如果没有超过 2说明当前窗口内水果的种类不超过两种直接更新结果 ret。1.2.2 算法流程a. 初始化哈希表 hash 来统计窗口内水果的种类和数量b. 初始化变量左右指针 left 0right 0记录结果的变量 ret 0c. 当 right 小于数组大小的时候一直执行下列循环i. 将当前水果放入哈希表中ii. 判断当前水果进来后哈希表的大小● 如果超过 2○ 将左侧元素滑出窗口并且在哈希表中将该元素的频次减一○ 如果这个元素的频次减一之后变成了 0就把该元素从哈希表中删除○ 重复上述两个过程直到哈希表中的大小不超过 2iii. 更新结果 retiv. right让下一个元素进入窗口d. 循环结束后ret 存的就是最终结果。1.3 代码classSolution{public:inttotalFruit(vectorintfruits){intmap[100000]{0};intkind0;//统计当前区间内水果的种类intl0,r0;intnfruits.size();intret0;while(rn){//进窗口if(map[fruits[r]]0)kind;while(kind2)//窗口不合法 -- 水果种类大于2{if(map[fruits[l]]--1)kind--;}retmax(ret,r-l1);r;}returnret;}};时间复杂度: O(n)二、找到字符串中所有字母的异位词2.1 题目链接找到字符串中所有字母的异位词2.2 算法原理核心思想滑动窗口 哈希表2.2.1 算法思路异位词本质就是在一段区间内各个元素出现的次数和p字符串里各元素出现的次数相同2.2.2 算法流程2.2.2.1 法一定义连个变量l,r来标识合法区间定义两个哈希表一个用来统计p串内各个元素出现的次数另一个用来统计【l,r】区间内各个元素出现的次数并且和另一个哈希表做比较看两个哈希表是否完全相同2.2.2.2 法二在法一的基础上定义个count来统计s中【l,r】有效字符个数的数量.最后和p元素长度作比较即可有效字符个数是在当前s串中的【l,r】区间中当该元素数量小于等于p串中该元素的数量则count加一如果【lr】是p的异位词则p的长度m必定和count相等。2.3 代码2.3.1 法一代码classSolution{public:vectorintfindAnagrams(string s,string p){vectorintret;inthash1[26]{0};//统计p各元素出现次数inthash2[26]{0};//统计s各元素出现次数for(inti0;ip.size();i)hash1[p[i]-a];intl0,r0,ns.size(),mp.size();while(rn){//进窗口charchs[r];hash2[ch-a];if(r-l1m)//出窗口hash2[s[l]-a]--;intf1;for(inti0;i26;i){if(hash1[i]!hash2[i]){f0;break;}}if(f)ret.push_back(l);r;}returnret;}};2.3.2 法二代码classSolution{public:vectorintfindAnagrams(string s,string p){vectorintret;inthash1[26]{0};//统计p各元素出现次数inthash2[26]{0};//统计s各元素出现次数for(inti0;ip.size();i)hash1[p[i]-a];intl0,r0,ns.size(),mp.size();intcount0;//统计当前【lr】区间内有效字符的个数while(rn){//进窗口charch1s[r];if(hash2[ch1-a]hash1[ch1-a])count;if(r-l1m)//出窗口{charch2s[l];if(hash2[ch2-a]--hash1[ch2-a])count--;}if(countm)ret.push_back(l);r;}returnret;}};时间复杂度: ON总结与每日励✨本文通过两道典型题目梳理滑动窗口核心逻辑可变窗口动态收缩左边界限制窗口内元素种类定长窗口维持固定区间搭配哈希统计字符频次。优化解法引入计数变量省去逐一枚举 26 个字母比对进一步简化逻辑。两类题目均仅一次遍历数组时间复杂度稳定 O (n)。掌握窗口伸缩规则与哈希表状态维护就能快速应对绝大多数滑动窗口题型。代码一行行敲算法一道道啃所有看似晦涩的逻辑都会在反复练习中变得通透。不必畏惧刷题路上的卡顿与报错每一次调试都是沉淀。沉下心深耕基础稳步积累那些默默付出的时光终会化作面试与竞赛里稳稳的底气永远相信美好的事情即将发生。