412 字
2 分钟
209. 长度最小的子数组
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]输出：2解释：子数组 [4,3] 是该条件下的长度最小的子数组。示例 2：
输入：target = 4, nums = [1,4,4]输出：1示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]输出：0思路
- 由于数组为连续数组，使用滑动窗口进行遍历。
注意，原题是大于等于，不是等于！！！。
代码流程
- 创建双指针
left, right，创建一个数字记录滑动窗口大小。窗口为左闭右开区间。 - 从左往右遍历。
- 如果当前数值小，增加right，更新数值。
- 如果当前数值大于等于，记录
right - left，增加left，更新数值。 - 如果
right == nums.size() && total < target遍历结束，返回0
- 边界条件
right == nums.size()- 数值小于target，手动退出循环
- 数值大于等于target，记录长度，移动left减小窗口大小。
class Solution {public: int minSubArrayLen(int target, vector<int>& nums) { int left = 0; int right = 0; int n = nums.size(); int total = 0; int res = INT_MAX;
while (right <= n) { // 左闭右开 if(total < target){ // 边界条件，如果right到末尾仍然小于，不允许再访问，直接退出。 if(right == n){ break; } total += nums[right]; right++; } else{ res = min(res, right - left); total -= nums[left]; left++; } }
return res == INT_MAX ? 0 : res; }};