209. 长度最小的子数组

题目链接：209. 长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0。

核心思考：滑动窗口的高效收缩

这道题目是经典的滑动窗口 (Sliding Window) 应用。我们的目标是找到一个满足条件的最小窗口。

与“固定窗口”不同，这里的窗口大小是动态变化的。核心逻辑在于：

1. 右指针 (right) 不断向右移动以扩大窗口，直到满足（或尽可能接近）条件。
2. 左指针 (left) 在满足条件的前提下，不断向右移动以缩小窗口，从而寻找“最小长度”。

优化点

在代码实现中，我们可以通过判断 s - nums[left] >= target 来决定是否可以安全地弹出左侧元素，这样可以保证在更新 ans 之前，窗口已经收缩到了满足条件的最小状态。

解题思路 (Python)

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        ans = n + 1  # 初始化为一个不可能达到的最大值
        s = 0        # 当前窗口内的元素之和
        left = 0     # 窗口左指针
        
        for right, x in enumerate(nums):
            s += x   # 右指针向右移动，累加当前数值
            
            # 如果减去窗口最左侧的数后，和依然大于等于 target
            # 说明我们可以进一步收缩窗口以寻求更小的长度
            while s - nums[left] >= target:
                s -= nums[left]
                left += 1
            
            # 只要当前窗口和满足条件，就尝试更新最小长度
            if s >= target:
                ans = min(ans, right - left + 1)
                
        return ans if ans <= n else 0

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组的长度。虽然嵌套了 while 循环，但每个元素最多被访问两次（进入窗口一次，离开窗口一次）。
• 空间复杂度：$O(1)$，仅使用了几个辅助变量。

C++ 实现

在 C++ 中，我们可以使用类似的逻辑。注意处理和可能超过 int 范围的情况（虽然本题 target 和元素均为正整数且范围适中，但使用 long long 或 int 均可，取决于题目约束）。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int left = 0;
        int sum = 0;
        int ans = n + 1;
        
        for (int right = 0; right < n; right++) {
            sum += nums[right];
            // 标准滑动窗口收缩逻辑
            while (sum >= target) {
                ans = min(ans, right - left + 1);
                sum -= nums[left++];
            }
        }
        
        return ans > n ? 0 : ans;
    }
};

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

n
num1 num2 num3 ... numN
target

第一行输入数组长度 n，第二行输入 n 个整数，第三行输入目标值 target。

完整代码：

import sys

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    n = len(nums)
            ans = n + 1  # 初始化为一个不可能达到的最大值
            s = 0        # 当前窗口内的元素之和
            left = 0     # 窗口左指针

            for right, x in enumerate(nums):
                s += x   # 右指针向右移动，累加当前数值

                # 如果减去窗口最左侧的数后，和依然大于等于 target
                # 说明我们可以进一步收缩窗口以寻求更小的长度
                while s - nums[left] >= target:
                    s -= nums[left]
                    left += 1

                # 只要当前窗口和满足条件，就尝试更新最小长度
                if s >= target:
                    ans = min(ans, right - left + 1)

            return ans if ans <= n else 0

def main():
    lines = sys.stdin.read().strip().split()
    n = int(lines[0])
    nums = list(map(int, lines[1:1+n]))
    target = int(lines[1+n])

    sol = Solution()
    result = sol.minSubArrayLen(nums, target)
    print(result)

if __name__ == "__main__":
    main()

运行示例：

echo -e "5\n2 7 11 15\n9" | python solution.py