LeetCode 209：长度最小的子数组（滑动窗口） —— 题解

👋 欢迎阅读

一.题目

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 = 0，right = 0。

• 右指针right从 0 到 n-1 依次遍历，将nums[right]加入窗口和sum。

• 每加入一个元素后，检查当前窗口和是否 ≥ target：

  • 若是，则尝试收缩左指针（left++）来缩小窗口，同时更新最小长度len = min(len, right-left+1)。

  • 重复收缩直到窗口和 < target。

• 遍历结束后，若len仍为INT_MAX，返回 0；否则返回len。

示例执行过程（target = 7, nums = [2, 3, 1, 2, 4, 3]）：

最终len = 2，对应子数组[4, 3]，返回 2。

三、正确性说明（简单版本）

滑动窗口利用所有数为正的性质，保证了窗口和是右指针的单调增函数。当窗口和 ≥ target 时，当前窗口是满足条件且以right为右端点的最短窗口（因为一旦和满足，我们就不断收缩左指针，直到刚好不满足，此时窗口长度就是该右端点下的最短长度）。由于我们遍历所有可能的右端点，并记录每个右端点下的最短长度，取全局最小值，因此不会遗漏任何候选子数组。该算法正确性由滑动窗口的单调性和遍历完整性保证。

四、实现细节（边界防护）

• 初始化left = 0，sum = 0，len = 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, vector<int>& 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; vector<int> nums = {2, 3, 1, 2, 4, 3}; Solution sol; int result = sol.minSubArrayLen(target, nums); cout << result << endl; // 输出 2 return 0; }

四、易错点分析

4.1 收缩窗口时使用while而非if

while (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^9，sum使用int是否会溢出？需要改用long long吗？

📚延伸挑战

• 如果题目要求返回满足和 >= target 的子数组的起始和结束下标（而不是长度），代码应做哪些调整？

• 如果要求找到和恰好等于 target 的最短子数组（而非大于等于），滑动窗口应如何修改？

如果你觉得本文对你有所帮助，欢迎：

👍点赞 / 收藏
👤关注作者，获取更多题解
💬留言交流你的疑问或优化思路

📌深入思考答案

• 收缩左指针是因为当前窗口已经满足条件，为了找到更短的子数组，需要尝试去掉左侧元素，在保持和 >= target 的前提下缩短窗口长度，这是滑动窗口寻找最小窗口的核心操作。

• 若存在负数，窗口和不再单调（加入负数可能使和减小），此时滑动窗口的收缩条件失效（和减少后可能再次满足条件，需要重新扩展），算法会出错，因此本题明确限定数组为正整数。

• 返回 0 是正确的，因为INT_MAX表示未找到任何满足条件的子数组，题意明确要求不存在时返回 0。

• O(n) 在时间上优于 O(n log n)，但进阶要求可能是为了考查多种解法的掌握（如前缀和+二分），实际应用中 O(n) 已最优，进阶属于拓展思维。

• nums[i]最大10^4，n最大10^5，窗口和最大10^9，仍在 32 位 int 范围内（约 21 亿），因此int足够安全，无需long long。

🔍延伸挑战答案

• 挑战1：只需在更新len时同时记录left和right作为起始和结束下标，最后返回该对下标即可，其他逻辑不变。

• 挑战2：若要求和恰好等于target，当窗口和大于 target 时不能直接收缩，因为和可能因后续加入负数而变小（但本题全为正数，因此一旦和大于 target，收缩左指针无法再回到恰好值），需要改用前缀和 + 哈希或双指针配合额外判断，滑动窗口不再适用。

祝你在算法之路上越走越稳，早日攻克每一道难题！下次见 🚀✨