LeetCode 209. 长度最小的子数组

◎

本节目标

在正整数数组中用可变长度窗口寻找和至少为目标值的最短连续子数组。

这道题是滑动窗口解题框架的最短可行窗口母题。窗口和一旦达到目标，就立刻尝试从左侧收缩。

查看原题

题意与约束

给定由正整数构成的数组 nums 和正整数 target，返回和大于等于 target 的最短非空连续子数组长度；不存在时返回 0。

正整数是本题能使用普通滑动窗口的关键约束：右移右边界只会让窗口和增大，右移左边界只会让窗口和减小。

从枚举起点到复用窗口

朴素做法枚举每个左端点，再向右累加，直到总和达到目标；即使总和按右端增量维护，最坏仍要检查 O(n²) 个区间。相邻起点会重新累加大量相同元素，这些重复工作正是瓶颈。

由于数组元素全为正数，右端加入元素只会增大总和；窗口已经可行时，左端右移又只会减小总和。因此两个边界都无需回退，可以复用上一轮的窗口和，用一次滑动扫描替代按起点重复枚举。

何时记录最短答案

右端加入一个数后，若窗口和仍小于目标，必须继续扩张。若窗口和已经达到目标，当前窗口可行，但可能还不够短；此时记录长度，移除左端元素，再检查是否仍可行。

在每个可行状态都重复这一步，就不会漏掉同一右端下更短的答案。左端移走后总和变小，最终会回到不可行状态，等待右端再次扩张。

代码实现

两份源码维护当前窗口和。哨兵初值表示尚未找到可行窗口，最后统一转换为 0。

C++

C++17

#include <algorithm>
#include <climits>
#include <vector>
using namespace std;

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0;
        int sum = 0;
        int best = INT_MAX;

        for (int right = 0; right < static_cast<int>(nums.size()); right++) {
            sum += nums[right];
            // 所有数为正时，收缩窗口不会错过更短可行解。
            while (sum >= target) {
                best = min(best, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return best == INT_MAX ? 0 : best;
    }
};

Python

Python 3

class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        left = 0
        total = 0
        best = len(nums) + 1

        for right, value in enumerate(nums):
            total += value
            # 所有数为正时，收缩窗口不会错过更短可行解。
            while total >= target:
                best = min(best, right - left + 1)
                total -= nums[left]
                left += 1
        return 0 if best == len(nums) + 1 else best

复杂度分析

• 时间复杂度：O(n)。每个元素最多被右端加入一次、被左端移除一次。
• 空间复杂度：O(1)。只维护边界、窗口和与最优长度。

易错点

• 找到第一个可行窗口就停止；最短答案常在后续收缩时出现。
• 更新答案后不移出左端元素，循环无法寻找更短窗口。
• 忽略正整数前提；如果数组含负数，窗口和不再随边界单调变化，需要其他方法。

模式迁移

满足条件后持续收缩的结构适用于最短覆盖、至少包含若干不同元素、窗口和或乘积达到阈值等问题。迁移时只需替换可行条件和窗口状态，并确认左移能否保持所需的单调性。