长度最小的子数组-LeetCode

209. 长度最小的子数组 - Minimum Size Subarray Sum

🎯 问题描述（来源于LeetCode）

描述：
给定一个含有 n 个正整数的数组 nums 和一个正整数 target。
找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。
如果不存在符合条件的子数组，返回 0。

说明：

• 子数组是连续的。
• 所有元素均为正整数。

示例：

• 示例 1：

输入: target = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 的长度为 2，其和为 7，是最短的。

• 示例 2：

输入: target = 4, nums = [1,4,4]
输出: 1

• 示例 3：

输入: target = 11, nums = [1,1,1,1,1,1,1,1]
输出: 0

💻 解题思路

思路：滑动窗口（双指针）

算法步骤

1. 初始化左指针 left = 0，当前窗口和 cur_sum = 0，最小长度 min_len = inf。
2. 右指针 right 从 0 到 n-1 遍历：
   • 将 nums[right] 加入窗口和 cur_sum。
   • 当 cur_sum >= target 时，尝试缩小窗口：
     • 更新 min_len = min(min_len, right - left + 1)。
     • 将 nums[left] 从窗口和中减去，左指针右移 left += 1。
3. 循环结束后，若 min_len 仍为 inf，返回 0；否则返回 min_len。

代码实现

from typing import List

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = 0
        n = len(nums)
        cur_sum = 0
        min_len = float('inf')
        for right, num in enumerate(nums):
            cur_sum += num
            while cur_sum >= target:
                min_len = min(min_len, right - left + 1)
                cur_sum -= nums[left]
                left += 1
        return min_len if min_len <= 10**5 else 0

📊 性能分析

• 时间复杂度：$O(n)$，每个元素最多被左右指针各访问一次。
• 空间复杂度：$O(1)$，仅使用常数个变量。

思考

滑动窗口是处理连续子数组和问题的经典技巧，利用双指针在 O(n) 时间内求解。代码中的 min_len <= 10**5 判断可简化为 min_len != inf，因为数组长度最大为 10^5，但原写法也能正确判断是否存在。整体逻辑清晰，是本题的标准解法。