滑动窗口求最小长度子数组完整代码#includestdio.h// 滑动窗口函数求满足和≥s的最短连续子数组长度intminSubArr(intnums[],intn,ints){// 记录最短窗口长度初始赋值n1一个不可能达到的超大值intminLenn1;// sum当前窗口内所有数字累加和left窗口左边界下标intsum0,left0;// right窗口右边界不断向右扩张窗口for(intright0;rightn;right){// 把右边界新元素加入窗口总和窗口向右扩大一格sumnums[right];// 只要当前窗口总和≥目标s就尝试收缩左边界找更短窗口while(sums){// 计算当前窗口长度右下标 - 左下标 1intcurLenright-left1;// 如果当前窗口比之前记录的最短窗口更小更新最小长度if(curLenminLen)minLencurLen;// 收缩左边界减去左边界元素左指针右移sum-nums[left];}}// 三元表达式如果minLen还是初始超大值说明没找到合法子数组返回0否则返回最短长度returnminLenn1?0:minLen;}intmain(){// 测试数组全部为正整数intarr[]{2,3,1,2,4,3};// 目标和子数组总和需要≥7ints7;// 计算数组总元素个数数组总字节 ÷ 单个int字节intlensizeof(arr)/sizeof(arr[0]);// 调用函数并打印结果printf(%d,minSubArr(arr,len,s));return0;}一、先搞懂要求底层前提输入全是正整数的数组、目标数字s需求找一段连续的子数组子数组所有数字相加 ≥s要求这段子数组长度尽可能短输出最短长度如果所有数字加起来都不够s输出0示例数组[2,3,1,2,4,3]s7合法子数组[2,3,1,2](和8长4)、[3,1,2,4](和10长4)、[1,2,4](和7长3)、[2,4,3](和9长3)、[4,3](和7长2)最短长度是2程序最终输出2关键前置知识点滑动窗口同向双指针滑动窗口 用left左指针、right右指针框出一段连续区间窗口右指针right扩张窗口不断往右走把新数字纳入窗口左指针left收缩窗口当窗口总和达标后不断往右缩寻找更短区间核心优势left和right只会向右走不会回头所有元素最多遍历2次 → 时间复杂度 O(n)比双重循环暴力枚举O(n²)快得多本题必须数组全为正数如果存在负数左指针右移后总和可能变大while循环会无限死循环二、详细解析 minSubArr 函数1. 函数头int minSubArr(int nums[], int n, int s)int nums[]传入需要处理的数组C语言中数组形参本质是指针接收数组首地址int n数组一共有多少个元素长度int s目标和子数组总和需要≥s返回值int满足条件的最短子数组长度无合法子数组返回02.int minLen n1;minLen全局记录目前找到的最短合法窗口长度初始值n1数组最长只有n个元素n1是绝对不可能出现的长度相当于“无穷大”标记作用循环结束后通过判断minLen是否等于n1区分有没有找到合法子数组3.int sum0, left0;sum累加器只计算当前窗口[left, right]内部所有数字的和不用每次重新求和节省计算left窗口左边界下标初始在数组最开头0只向右移动绝不回退4.for(int right0;rightn;right)外层循环控制窗口右边界right窗口右边界下标从0开始遍历到数组最后一位n-1每一轮循环窗口向右扩张一格把nums[right]纳入窗口right只会递增不会回到左边保证复杂度O(n)5.sum nums[right];扩张窗口操作把当前右指针指向的数字加到窗口总和sum里窗口范围变成[left, right]6.while(sum s)这是滑动窗口精髓达标后收缩窗口优化最短长度只要当前窗口总和满足sum ≥ s就进入循环不断压缩左边界逻辑当前窗口已经满足要求我们尝试丢掉左边数字看能不能得到更短、同样满足条件的窗口为什么用while不用if丢掉一个左边元素后总和可能依旧≥s需要继续缩直到总和不足s才停止7.int curLen right - left 1;计算当前窗口真实长度数组下标是从0开始区间[left, right]包含元素个数 右 - 左 1例left4right5 → 5-412对应元素nums[4]、nums[5]长度28.if(curLen minLen) minLen curLen;更新最短长度如果当前收缩后的窗口长度比之前记录的最小长度更小就覆盖minLen保存当前最优解9.sum - nums[left];两步操作合并sum - nums[left]把窗口最左侧的数字从总和中剔除窗口丢掉左边元素left左边界向右移动一格窗口整体缩小left后置自增先使用left原值计算再自增110.return minLenn1 ? 0 : minLen;三元运算符判断结果如果循环全程minLen一直是初始值n1说明没有任何一段子数组总和≥s返回0如果minLen被更新过说明找到合法窗口返回记录的最短长度三、main函数逐行解析int arr[]{2,3,1,2,4,3};定义测试数组全部为正整数长度自动推导为6int s7;设定目标和子数组累加需要≥7int len sizeof(arr)/sizeof(arr[0]);计算数组元素总数sizeof(arr) 整个数组占用字节数6个int24字节sizeof(arr[0]) 单个int占用4字节24 / 4 6得到数组长度6printf(%d, minSubArr(arr, len, s));调用滑动窗口函数打印返回的最短长度2return 0;程序正常结束返回0给操作系统四、完整手动模拟全过程arr[2,3,1,2,4,3], n6, s7初始状态minLen7sum0left0第1轮 right0sum 2 → sum2sum2 7不进入while直接下一轮窗口[0,0]第2轮 right1sum 3 → sum5sum5 7不进入while窗口[0,1]第3轮 right2sum 1 → sum6sum6 7不进入while窗口[0,2]第4轮 right3sum 2 → sum8 ≥7进入while循环curLen3-014minLen4sum - nums[0]2 → sum6left1sum6 7退出while窗口[1,3]第5轮 right4sum 4 → sum6410 ≥7进入while第一次循环curLen4-1144不小于minLen(4)不更新sum - nums[1]3 → sum7left2sum7仍≥7继续循环第二次循环curLen4-21334 → minLen3sum - nums[2]1 → sum6left3sum67退出while窗口[3,4]第6轮 right5sum 3 → sum639 ≥7进入while第一次循环curLen5-313不小于minLen(3)不更新sum - nums[3]2 → sum7left4sum7≥7继续循环第二次循环curLen5-41223 → minLen2sum - nums[4]4 → sum3left5sum37退出whilefor循环全部结束minLen2不等于初始值7返回2打印结果2五、补充关键细节易错点1. 为什么数组必须是正整数如果数组存在负数左指针右移剔除元素后总和可能变大while(sum s)会无限循环卡死程序。本题题目明确限定正整数数组才能使用该滑动窗口写法。2. 两层循环为什么复杂度还是O(n)right从0走到n-1最多移动n次left只会向右移动全程最多移动n次。两个指针合计最多移动2n次没有嵌套遍历复杂度O(n)。对比暴力双重循环外层起点left内层终点right最坏O(n²)数据量大时会超时。3. 初始化minLen为什么用n1不能用00代表长度会干扰最小值判断不能用INT_MAX普通int数组场景用n1更直观代表“不存在”的标记。4. 窗口长度计算公式 right-left1 为什么要1下标差值是元素间隔不是元素个数。例如下标4、5两个元素5-41实际2个元素必须1。5. 什么时候函数返回0数组所有数字相加总和 s没有任何子数组满足条件minLen全程保持n1触发三元表达式返回0。六、代码运行结果输出2