01_fixed_slide_win.md 定长滑动窗口刷题笔记C语言完整版代码链接https://gitee.com/hiwangGitee/0x3f-algorithm-c/tree/main/通用模板核心定长滑动窗口通用公式left i - k 1通用执行流程元素入窗统计 → 窗口满长更新答案 → 滑出左边界平移窗口定长滑动窗口专题总结通用核心公式left i - k 1所有题目统一窗口逻辑仅内部统计逻辑不同题型分类1. 数值求和/最值643、1052适合数组区间统计2. 字符计数最值1456、2379简单字符统计窗口3. 频次匹配类567、43826字母桶匹配异位词4. 字符串哈希查重187固定长度子串去重统计。模板复用性全部题目遵循「入窗统计 → 窗口满更新答案 → 出窗平移」流程可直接作为刷题万能模板。全局公共头文件#includestdio.h// 标准输入输出printf/scanf必备#includestdlib.h// malloc/free、exit()、rand()#includestring.h// 字符串函数 strlen/strcpy/memset#includectype.h// 字符判断 isdigit/isalpha#includemath.h// 数学函数 sqrt/sin/cos#includetime.h// 时间相关 time()#includestdbool.h// C99 布尔类型 bool true/false#includelimits.h#includeuthash.h643 子数组最大平均数 I题目链接https://leetcode.cn/problems/maximum-average-subarray-i/题目描述给你一个由n个元素组成的整数数组nums和一个整数k。请你找出平均数最大、且长度为k的连续子数组输出该最大平均数。答案误差小于10^-5 即判定正确。示例示例1输入nums [1,12,-5,-6,50,3], k 4输出12.75解释最优子数组和KaTeX parse error: Undefined control sequence: \- at position 3: 12\̲-̲5\-6\5051平均数51/4127˙551/412\.7551/4127˙5示例2输入nums [5], k 1输出5.00000核心考点定长滑动窗口入门模板、增量维护窗口和、线性时间遍历优化1. 公式含义left i - k 1当前右边界下标i窗口固定长度k窗口左边界下标 右边界 - 窗口长度 1举例i3、k4样例 1 第 4 个元素left3-410窗口范围[0,3]正好 4 个元素完全匹配定长窗口区间。2. 分阶段作用阶段 1left 0窗口元素不足 k 个只累加元素、不做均值计算跳过滑出逻辑完成初始窗口填充阶段 2left ≥ 0窗口凑满 k 个元素立刻计算当前窗口平均数对比更新最大值随后剔除nums[left]、窗口整体右移一格开启下一轮迭代。代码实现doublefindMaxAverage(int*nums,intnumsSize,intk){doubleres0,resultINT_MIN;doublecnt0;intnum0;for(inti0;inumsSize;i){cntcntnums[i];numnum1;// 当前右边界下标i窗口固定长度k窗口左边界下标 右边界 - 窗口长度 1intlefti-k1;if(left0){continue;}rescnt/num;if(resresult){resultfmax(res,result);}cntcnt-nums[left];numnum-1;}returnresult;}1456 定长子串中元音的最大数目题目链接https://leetcode.cn/problems/maximum-number-of-vowels-in-a-substring-of-given-length/题目描述给定字符串s和整数k找出s所有长度固定为k的连续子串里包含元音字母a、e、i、o、u数量的最大值并返回。输入输出示例示例1输入s “abciiidef”, k 3 输出3 解释子串 “iii” 包含3个元音字母为全局最大值示例2输入s “aeiou”, k 2 输出2 解释任意长度为2的子串均包含2个元音字母示例3输入s “leetcode”, k 3 输出2 解释“lee”、“eet”、“ode” 这类子串元音数为当前最大的2示例4输入s “rhythms”, k 4 输出0 解释整串无元音字母结果为0示例5输入s “tryhard”, k 4 输出1核心考点定长滑动窗口基础应用用通用公式left i - k 1控制窗口边界增量维护窗口内元音计数线性遍历求解全局最大值代码实现boolisVowel(charc){returnca||ce||ci||co||cu;}intmaxVowels(char*s,intk){intlenstrlen(s);intwindowCnt0;intmaxCnt0;for(inti0;ilen;i){if(isVowel(s[i])){windowCnt;}intlefti-k1;if(left0){continue;}if(windowCntmaxCnt){maxCntwindowCnt;}if(isVowel(s[left])){windowCnt--;}}returnmaxCnt;}1052 爱生气的书店老板题目链接https://leetcode.cn/problems/grumpy-bookstore-owner/题目描述书店营业共n分钟-customers[i]第i分钟到店顾客数-grumpy[i]1老板该分钟生气顾客不满意grumpy[i]0老板不生气顾客满意老板可使用1次技能连续 minutes 分钟强制不生气原本生气时段的顾客也会满意。求全天最多能收获的满意顾客总数。输入输出示例示例1输入customers [1,0,1,2,1,1,7,5]grumpy [0,1,0,1,0,1,0,1]minutes 3 输出16 解释技能作用于最后3分钟原本不生气时段顾客照常满意原本生气的3段顾客被额外挽救累加得到最大值16示例2输入customers [1], grumpy [0], minutes 1 输出1 解释原本老板就不生气技能不改变结果解题思路拆解1. 基础满意值求和先累加所有grumpy[i]0位置的顾客这部分不受技能影响2. 定长滑窗求增量最大值窗口长度固定为minutes只统计窗口内grumpy[i]1的顾客和使用技能能额外挽救的人数用left i - minutes 1经典定长窗口公式遍历3. 最终答案 基础满意值 最大可挽救增量。核心考点定长滑动窗口求区间最值、拆分固定收益窗口浮动增量的两步解题模型线性时间遍历优化代码实现intmaxSatisfied(int*customers,intcustomersSize,int*grumpy,intgrumpySize,intminutes){intmax_s0;intbase0,add_cnt0;for(inti0;icustomersSize;i){if(grumpy[i]0){basecustomers[i];}}// 选一段长度严格等于 minutes 的连续区间// 区间内原本grumpy[i]1生气流失的顾客全部变成满意顾客for(inti0;icustomersSize;i){if(grumpy[i]1){add_cntcustomers[i];// 增益值益值 窗口内原本生气grumpy[i]1的顾客数}intlefti-minutes1;// 窗口左端点if(left0){// 窗口长度不足 minutescontinue;}max_sfmax(max_s,add_cnt);if(grumpy[left]1){add_cnt-customers[left];}}returnbasemax_s;}2379 得到 K 个黑块的最少涂色次数题目链接https://leetcode.cn/problems/minimum-recolors-to-get-k-consecutive-black-blocks/题目描述给定长度为n、仅由W白色块和B黑色块组成的字符串blocks每次操作可把白色块涂成黑色块。要求字符串中至少出现一段连续k个黑色块求需要的最少涂色次数。输入输出示例示例1输入blocks “WBBWWBBWBW”, k 7 输出3 解释选取一段长度7的区间将区间内3个白块涂黑即可达成目标不存在操作次数更少的方案示例2输入blocks “WBWBBBW”, k 2 输出0 解释原字符串本身就存在连续2个黑块无需涂色操作解题思路拆解1. 问题等价转化任意一段长度固定为k的连续区间区间内白色块数量就是把这段全部涂黑需要的操作次数题目求全局最小值2. 采用定长滑动窗口遍历所有长度k的区间用通用边界公式left i - k 1维护窗口3. 右指针入窗统计白块数量窗口满长后更新最小操作数再滑出左边界元素完成平移。核心考点定长滑动窗口计数求全局最小值入门级定长窗口模板应用题代码实现intminimumRecolors(char*blocks,intk){intlenstrlen(blocks);intwindowWhite0;intminOpk;for(inti0;ilen;i){if(blocks[i]W){windowWhite;}intlefti-k1;if(left0){continue;}if(windowWhiteminOp){minOpwindowWhite;}if(blocks[left]W){windowWhite--;}}returnminOp;}567 字符串的排列题目链接https://leetcode.cn/problems/permutation-in-string/题目描述给定两个字符串s1和s2判断s2是否包含s1的任意一种排列若存在返回true反之返回false。等价判定条件s1的某个排列能够作为s2的一段连续子串出现。输入输出示例示例1输入s1 “ab”s2 “eidbaooo” 输出true 解释s2 的子串 “ba” 是 s1 的排列形式之一示例2输入s1 “ab”s2 “eidboaoo” 输出false核心考点定长滑动窗口、字符频次统计比对窗口长度固定为 s1 长度通过对比窗口与目标字符串的字母频次判断是否为排列子串代码实现#defineCHAR_TOTAL26// 比对两个长度26的频次数组是否完全相等boolcountEqual(intcntA[],intcntB[]){for(intidx0;idxCHAR_TOTAL;idx){if(cntA[idx]!cntB[idx]){returnfalse;}}returntrue;}boolcheckInclusion(char*s1,char*s2){inttargetCnt[CHAR_TOTAL]{0};intwindowCnt[CHAR_TOTAL]{0};intkstrlen(s1);ints2Lenstrlen(s2);// s2更短直接不可能包含s1排列子串if(ks2Len){returnfalse;}// 统计s1目标频次for(inti0;ik;i){intcIdxs1[i]-a;targetCnt[cIdx];}for(inti0;is2Len;i){intcIdxs2[i]-a;windowCnt[cIdx];intlefti-k1;if(left0){continue;}// 当前窗口长度达标比对频次if(countEqual(windowCnt,targetCnt)){returntrue;}// 滑出左边界字符窗口右移intleftCIdxs2[left]-a;windowCnt[leftCIdx]--;}returnfalse;}438 找到字符串中所有字母异位词题目链接https://leetcode.cn/problems/find-all-anagrams-in-a-string/题目描述给定两个字符串s和p找出s中全部属于p字母异位词的连续子串返回所有对应起始下标结果顺序不作要求。字母异位词指字符种类、数量完全一致排列顺序不同的字符串。输入输出示例示例1输入s “cbaebabacd”, p “abc” 输出[0,6] 解释下标0子串cba、下标6子串bac都是abc的异位词示例2输入s “abab”, p “ab” 输出[0,1,2] 解释三处连续长度为2的子串均为目标异位词解题思路拆解1. 统计模式串p的字符频次作为匹配标准2. 以p的长度为固定窗口在字符串s上滑动3. 每次窗口满长后比对频次完全一致则记录当前左边界下标4. 窗口右移剔除左侧出窗字符频次继续遍历收集所有合法异位词下标。核心考点定长滑动窗口 26字母频次比对、多答案收集模板是567题的拓展升级版代码实现#defineNUM_2626boolcountEqual(inttargetCnt[],intwindowCnt[]){for(intidx0;idxNUM_26;idx){if(targetCnt[idx]!windowCnt[idx]){returnfalse;}}returntrue;}int*findAnagrams(char*s,char*p,int*returnSize){intsLenstrlen(s);intpLenstrlen(p);*returnSize0;if(pLensLen){returnNULL;}inttargetCnt[NUM_26]{0};intwindowCnt[NUM_26]{0};for(inti0;ipLen;i){intcp[i]-a;targetCnt[c];}int*resArr(int*)malloc(sizeof(int)*sLen);intkpLen;for(inti0;isLen;i){intcs[i]-a;windowCnt[c];intlefti-k1;if(left0){continue;}if(countEqual(targetCnt,windowCnt)){resArr[(*returnSize)]left;}intleftCs[left]-a;windowCnt[leftC]--;}returnresArr;}187 重复的DNA序列题目链接https://leetcode.cn/problems/repeated-dna-sequences/题目描述DNA 序列由 A、C、G、T 四种字符组成给定一个字符串s返回所有长度为 10 且出现次数大于等于 2 的子串返回结果无需有序。输入输出示例示例1输入s “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT” 输出[“AAAAACCCCC”,“CCCCCAAAAA”]示例2输入s “AAAAAAAAAAAAA” 输出[“AAAAAAAAAA”]解题思路拆解1. 固定窗口长度为 10遍历截取所有连续子串2. 借助 uthash 哈希表统计每个子串出现频次3. 仅收录首次达到两次的子串避免重复答案4. 遍历结束释放哈希内存避免内存泄漏。核心考点定长滑动窗口截取子串、uthash 字符串哈希频次统计、重复数据去重收集代码实现#defineNUM_1010#defineNUM_11(NUM_101)typedefstruct{charkey_val[NUM_11];intcnt;UT_hash_handle hh;}Node;Node*hash_tableNULL;char**findRepeatedDnaSequences(char*s,int*returnSize){*returnSize0;intsLenstrlen(s);if(sLenNUM_10){returnNULL;}char**resArr(char**)malloc(sizeof(char*)*(sLen-NUM_101));charsub[NUM_11];for(inti0;isLen;i){intlefti-NUM_101;if(left0){continue;}strncpy(sub,sleft,NUM_10);sub[NUM_10]\0;Node*nodeNULL;HASH_FIND(hh,hash_table,sub,NUM_11,node);if(node!NULL){node-cnt1;// 仅首次重复时收录答案if(node-cnt2){resArr[*returnSize](char*)malloc(NUM_11);strcpy(resArr[*returnSize],sub);(*returnSize);}}else{Node*newNode(Node*)malloc(sizeof(Node));strcpy(newNode-key_val,sub);newNode-cnt1;HASH_ADD(hh,hash_table,key_val,NUM_11,newNode);}}// 释放哈希表内存Node*cur,*tmp;HASH_ITER(hh,hash_table,cur,tmp){HASH_DEL(hash_table,cur);free(cur);}returnresArr;}