title: 每日一练（45）：长度最小的子数组
categories:[剑指offer]
tags:[每日一练]
date: 2022/04/19
每日一练（45）：长度最小的子数组
给定一个含有 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
提醒：
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
办法一：队列模仿滑动窗口
思路剖析
应用队列模仿滑动窗口，并应用一个sum记录队列内数的和，因为数的大小有别，所以这里应用while来推出队列中的数
int minSubArrayLen(int target, vector<int>& nums) { int ans = INT_MAX, sum = 0; queue<int> que; for (auto &n : nums) { sum += n; que.push(n); while (sum >= target) { ans > que.size() ? ans = que.size() : ans; sum -= que.front(); que.pop(); } } return ans == INT_MAX ? 0 : ans;}办法二：双指针
思路剖析
定义两个指针i和j指针，将区间[j,i]看成滑动窗口，那么两个指针就别离示意滑动窗口的开始地位和完结地位，同时咱们再保护一个sum变量用来存贮区间[j,i]间断数组的和。如果以后滑动窗口保护的区间和sum大于等于target，就阐明以后的窗口是可行的，可行中的长度最短的滑动窗口就是答案
int minSubArrayLen(int target, vector<int>& nums) { int res = INT_MAX, sum = 0; for (int i = 0, j = 0; i < nums.size(); i++) { sum += nums[i];//向右扩大窗口 while (sum - nums[j] >= target) {//向左膨胀窗口 sum -= nums[j++]; } if (sum >= target) {//区间更新 res = min(res, i - j + 1); } } return res == INT_MAX ? 0 : res;}