個(gè)人主頁(yè)：兜里有顆棉花糖
歡迎 點(diǎn)贊?? 收藏? 留言? 加關(guān)注??本文由 兜里有顆棉花糖 原創(chuàng)
收錄于專欄【手撕算法系列專欄】【LeetCode】
??本專欄旨在提高自己算法能力的同時(shí)，記錄一下自己的學(xué)習(xí)過(guò)程，希望對(duì)大家有所幫助
??希望我們一起努力、成長(zhǎng)，共同進(jìn)步。
點(diǎn)擊直接跳轉(zhuǎn)到該題目
1??題目描述
給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) target 。
找出該數(shù)組中滿足其總和大于等于 target 的長(zhǎng)度最小的 連續(xù)子數(shù)組 [nums[l], nums[l+1], ..., nums[r-1], nums[r]] ，并返回其長(zhǎng)度。如果不存在符合條件的子數(shù)組，返回 0 。
示例1：
輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(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 <= 10^91 <= nums.length <= 10^51 <= nums[i] <= 10^5
2??算法分析
解題思路如下：
- 步驟一：使用雙指針left和right來(lái)構(gòu)建滑動(dòng)窗口，初始時(shí)left和right都為0。
- 步驟二：進(jìn)入循環(huán)，將右指針right向右移動(dòng)，每次將nums[right]的值加到sum中。
- 步驟三：進(jìn)入while循環(huán)，判斷當(dāng)前窗口內(nèi)的和sum是否大于等于目標(biāo)值target。如果是，則更新ret為最小值，即min(ret, right - left + 1)；然后將左指針left向右移動(dòng)，并從sum中減去nums[left]。
-
然后循環(huán)步驟二和步驟三，
直到右指針right達(dá)到數(shù)組的末尾；最后返回結(jié)果即可。
3??代碼編寫
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int ret = INT_MAX, sum = 0;
for(int left = 0,right = 0;right < n;right++)
{
// 進(jìn)窗口
sum += nums[right];
while(sum >= target)
{
// 更新結(jié)果
ret = min(ret,right - left + 1);
// 出窗口
sum -= nums[left++];
}
}
return ret == INT_MAX ? 0 : ret;
}
};
最后就是通過(guò)啦！??！文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-720837.html
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-720837.html
到了這里，關(guān)于【算法|滑動(dòng)窗口No.1】leetcode209. 長(zhǎng)度最小的子數(shù)組的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
