title: 每日一練（45）：長(zhǎng)度最小的子數(shù)組
categories:[劍指offer]
tags:[每日一練]
date: 2022/04/19
每日一練（45）：長(zhǎng)度最小的子數(shù)組
給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) target 。
找出該數(shù)組中滿(mǎn)足其和 ≥ target 的長(zhǎng)度最小的 連續(xù)子數(shù)組 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其長(zhǎng)度舱馅。如果不存在符合條件的子數(shù)組，返回 0 目溉。
示例 1：
輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋?zhuān)鹤訑?shù)組 [4,3] 是該條件下的長(zhǎng)度最小的子數(shù)組。
示例 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
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
方法一：隊(duì)列模擬滑動(dòng)窗口
思路分析
使用隊(duì)列模擬滑動(dòng)窗口菱农，并使用一個(gè)sum記錄隊(duì)列內(nèi)數(shù)的和缭付，由于數(shù)的大小有別，所以這里使用while來(lái)推出隊(duì)列中的數(shù)
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;
}
方法二：雙指針
思路分析
定義兩個(gè)指針i和j指針循未，將區(qū)間[j,i]看成滑動(dòng)窗口陷猫，那么兩個(gè)指針就分別表示滑動(dòng)窗口的開(kāi)始位置和結(jié)束位置，同時(shí)我們?cè)倬S護(hù)一個(gè)sum變量用來(lái)存貯區(qū)間[j,i]連續(xù)數(shù)組的和的妖。如果當(dāng)前滑動(dòng)窗口維護(hù)的區(qū)間和sum大于等于target绣檬，就說(shuō)明當(dāng)前的窗口是可行的，可行中的長(zhǎng)度最短的滑動(dòng)窗口就是答案
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];//向右擴(kuò)展窗口
while (sum - nums[j] >= target) {//向左收縮窗口
sum -= nums[j++];
}
if (sum >= target) {//區(qū)間更新
res = min(res, i - j + 1);
}
}
return res == INT_MAX ? 0 : res;
}
