欢迎阅读一.题目209. 长度最小的子数组 - 力扣LeetCode​ 欢迎来到「长度最小的子数组」题解之旅本文将带你从“寻找和大于等于目标值的最短连续子数组”这一优化问题出发深入理解滑动窗口双指针的经典应用并掌握如何通过动态调整窗口边界在 O(n)O(n) 时间内找到最优解。在开始之前建议你先了解题目背景这是 LeetCode 209 题给定一个由正整数组成的数组nums和目标值target要求找到和 ≥ target 的最短连续子数组并返回其长度若不存在则返回0。由于数组中全是正数窗口和具有单调性——右指针扩展时和增大左指针收缩时和减小这为滑动窗口提供了天然的条件。明确学习目标掌握滑动窗口核心流程——右指针right不断向右扩展累加元素和一旦窗口内和 target就尝试收缩左指针left将左侧元素移出窗口在收缩过程中持续更新满足条件的最小窗口长度直到和再次小于target然后继续扩展右指针。理解为什么“右扩左缩”的策略能遍历所有可能的窗口并保证不漏解并熟练处理边界情况如无解返回0。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如target 7, nums [2,3,1,2,4,3]输出2。本文将从问题转化、滑动窗口策略设计右扩左缩、窗口收缩条件到代码实现层层递进。即使你对滑动窗口还不熟悉我们也会从“先扩展右边凑够目标再收缩左边找最短”这一直觉出发让你轻松抓住核心思想——利用正数数组的和单调性用双指针维护一个动态窗口在满足条件时不断压缩窗口从而找到全局最短。现在让我们一起在数组中滑动窗口找出那个和达标的最短子数组吧 二.做题思路一、问题分析前置分析给定一个正整数数组nums和一个正整数target要求找到和 ≥ target 的最短连续子数组返回其长度。若不存在返回 0。核心观察所有数均为正因此窗口内和随右指针扩大而单调递增随左指针收缩而单调递减。这正好适合滑动窗口双指针可以在 O(n) 时间内解决。二、算法策略滑动窗口使用左右指针left和right维护一个窗口初始left 0right 0。右指针right从 0 到 n-1 依次遍历将nums[right]加入窗口和sum。每加入一个元素后检查当前窗口和是否 ≥ target若是则尝试收缩左指针left来缩小窗口同时更新最小长度len min(len, right-left1)。重复收缩直到窗口和 target。遍历结束后若len仍为INT_MAX返回 0否则返回len。示例执行过程target 7, nums [2, 3, 1, 2, 4, 3]步骤right操作窗口[left, right]窗口和是否 ≥7操作后len初始---0-∞10加入2[0,0]2否∞21加入3[0,1]5否∞32加入1[0,2]6否∞43加入2[0,3]8是收缩左移0→1和6更新 len4继续收缩左移1→2和37 停止54加入4[2,4]7是收缩左移2→3和67 停止更新 len365加入3[3,5]9是收缩左移3→4和7≥7更新 len2再收缩左移4→5和37 停止最终len 2对应子数组[4, 3]返回 2。三、正确性说明简单版本滑动窗口利用所有数为正的性质保证了窗口和是右指针的单调增函数。当窗口和 ≥ target 时当前窗口是满足条件且以right为右端点的最短窗口因为一旦和满足我们就不断收缩左指针直到刚好不满足此时窗口长度就是该右端点下的最短长度。由于我们遍历所有可能的右端点并记录每个右端点下的最短长度取全局最小值因此不会遗漏任何候选子数组。该算法正确性由滑动窗口的单调性和遍历完整性保证。四、实现细节边界防护初始化left 0sum 0len INT_MAX。for (int right 0; right n; right)遍历sum nums[right]while (sum target)循环收缩len min(len, right - left 1)sum - nums[left]。循环结束后若len INT_MAX返回 0否则返回len。时间复杂度 O(n)每个元素最多入窗一次、出窗一次空间复杂度 O(1)。五、返回值目标映射返回len即满足条件的最短连续子数组长度。若不存在返回 0。三.代码#include iostream #include vector #include climits using namespace std; class Solution { public: int minSubArrayLen(int target, vectorint nums) { // 算法思路滑动窗口双指针 // 右指针不断向右扩展窗口累加元素和 // 一旦窗口内和 target就尝试收缩左指针缩小窗口 // 并在此过程中更新满足条件的最小窗口长度。 // 直到右指针到达数组末尾返回最小长度若不存在则返回0。 int n nums.size(); int sum 0; // 当前窗口内元素的和 int len INT_MAX; // 记录满足条件的最小窗口长度初始化为最大值 // 使用 for 循环右指针 right 从 0 到 n-1 遍历数组 for (int left 0, right 0; right n; right) { // 入窗口将 nums[right] 加入当前窗口的和 sum nums[right]; // 当窗口内和 target 时尝试收缩窗口寻找更短的满足条件的子数组 while (sum target) { // 更新最小长度当前窗口长度为 right - left 1 len min(len, right - left 1); // 出窗口将 nums[left] 从和中移除左指针右移 sum - nums[left]; left; } } // 如果 len 仍为 INT_MAX说明不存在这样的子数组返回0 if (len INT_MAX) { return 0; } // 否则返回最小长度 return len; } }; int main() { // 测试用例target 7, nums [2,3,1,2,4,3]期望输出 2 int target 7; vectorint nums {2, 3, 1, 2, 4, 3}; Solution sol; int result sol.minSubArrayLen(target, nums); cout result endl; // 输出 2 return 0; }四、易错点分析4.1 收缩窗口时使用while而非ifwhile (sum target) { len min(len, right - left 1); sum - nums[left]; left; }易错原因当窗口和满足条件时需要持续收缩左指针直到窗口和小于target因为要找到以当前right结尾的最短子数组。若误写成if只收缩一次则只能得到一个满足条件的窗口但可能不是最短的例如窗口内元素全为正数收缩一次后和仍 ≥ target此时更短的窗口未被记录。必须用while不断尝试收缩确保每个右边界下都找到最小长度。4.2 更新len的位置应在收缩窗口循环内部while (sum target) { len min(len, right - left 1); sum - nums[left]; left; }易错原因len必须在每次收缩时更新因为每收缩一次都可能产生更短的满足条件的子数组。若将len更新写在while循环外面如紧跟在for循环内、while之后则只会记录第一次满足时的长度后续收缩得到的更短长度会被遗漏。正确做法是将len更新放在while循环体的第一行确保每次左指针移动前都记录当前窗口长度。4.3 左指针自增时sum的减操作顺序sum - nums[left]; left;易错原因出窗口时必须先用nums[left]减去当前值再left。若顺序写反先left再sum - nums[left]则减去的是下一个元素的值导致窗口和计算错误。虽然本题中left后减的是新位置的元素看似sum变化但逻辑完全错误会漏掉原本left位置的元素使窗口和偏小最终可能漏解或得到错误的最小长度。务必记住先减后移。五、流程图 闭幕 恭喜你完成了「长度最小的子数组」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题使用滑动窗口右指针不断扩展当窗口和 target 时尝试收缩左指针。请问为什么窗口和满足条件后要收缩左指针收缩的目的是什么如果数组元素全是正数滑动窗口可以保证单调性窗口和随右移增大随左移减小。如果数组中存在负数当前算法是否仍然正确为什么代码中len初始化为INT_MAX最后判断是否变化。如果target很小整个数组和都小于 target此时len保持INT_MAX返回 0这个处理是否正确滑动窗口的时间复杂度为O(n)而题目进阶要求 O(n log n) 解法如前缀和 二分。请思考在什么情况下 O(n) 比 O(n log n) 更优为什么本题仍给出进阶要求如果数组长度为10^5每个元素最大10^4窗口和最大为10^9sum使用int是否会溢出需要改用long long吗延伸挑战如果题目要求返回满足和 target 的子数组的起始和结束下标而不是长度代码应做哪些调整如果要求找到和恰好等于 target 的最短子数组而非大于等于滑动窗口应如何修改如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案收缩左指针是因为当前窗口已经满足条件为了找到更短的子数组需要尝试去掉左侧元素在保持和 target 的前提下缩短窗口长度这是滑动窗口寻找最小窗口的核心操作。若存在负数窗口和不再单调加入负数可能使和减小此时滑动窗口的收缩条件失效和减少后可能再次满足条件需要重新扩展算法会出错因此本题明确限定数组为正整数。返回 0 是正确的因为INT_MAX表示未找到任何满足条件的子数组题意明确要求不存在时返回 0。O(n) 在时间上优于 O(n log n)但进阶要求可能是为了考查多种解法的掌握如前缀和二分实际应用中 O(n) 已最优进阶属于拓展思维。nums[i]最大10^4n最大10^5窗口和最大10^9仍在 32 位 int 范围内约 21 亿因此int足够安全无需long long。延伸挑战答案挑战1只需在更新len时同时记录left和right作为起始和结束下标最后返回该对下标即可其他逻辑不变。挑战2若要求和恰好等于target当窗口和大于 target 时不能直接收缩因为和可能因后续加入负数而变小但本题全为正数因此一旦和大于 target收缩左指针无法再回到恰好值需要改用前缀和 哈希或双指针配合额外判断滑动窗口不再适用。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨