力扣 长度最小的子数组

一、题目概述

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

二、问题分析

1， 连续子数组 + 求最小长度

题目要求的是：

• 连续子数组（不是子序列）

• 和 ≥ target

• 长度最小

这三个条件共同决定了本题非常适合使用滑动窗口（双指针）方法。

2， 为什么不能暴力枚举？

暴力做法是：

• 枚举所有子数组

• 计算每个子数组的和

时间复杂度为：

O(n²)

在数据规模较大时必然超时 ❌。

三、滑动窗口核心思想

滑动窗口的本质

维护一个区间[left, right]，并保证：

• right向右扩展：增加窗口内的元素

• 当窗口内的和 ≥ target时：

  • 尝试移动left缩小窗口

  • 更新最小长度

适用条件

⚠️本题能够使用滑动窗口的关键前提是：

数组中的元素全部为正整数

因为只有正整数，窗口右移时，区间和才会单调递增，
左移时才会单调递减。

四、算法步骤详解

1. 初始化：

   • left = 0

   • sum = 0

   • ans = n + 1（表示未找到）

2. right从0开始遍历数组：

   • 将nums[right]加入sum

3. 当sum >= target时：

   • 更新最小长度：ans = min(ans, right - left + 1)

   • 移动left，缩小窗口：sum -= nums[left] left++

4. 遍历结束： 如果ans未更新，返回0否则返回ans

五、代码

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]; left++; } } return ans == n + 1 ? 0 : ans; } };