題目

給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) target 。
找出該數(shù)組中滿足其和 ≥ target 的長度最小的 連續(xù)子數(shù)組 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其長度。如果不存在符合條件的子數(shù)組，返回 0 。

參考【代碼隨想錄】

示例 1：

輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長度最小的子數(shù)組。

示例 3：

輸入：target = 11, nums = [1,1,1,1,1,1,1,1]
輸出：0

提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

思路

滑動窗口
接下來就開始介紹數(shù)組操作中另一個重要的方法：滑動窗口。

所謂滑動窗口，就是不斷的調(diào)節(jié)子序列的起始位置和終止位置，從而得出我們要想的結(jié)果。

首先要思考 如果用一個for循環(huán)，那么應(yīng)該表示 滑動窗口的起始位置，還是終止位置。

如果只用一個for循環(huán)來表示 滑動窗口的起始位置，那么如何遍歷剩下的終止位置？

所以 只用一個for循環(huán)，那么這個循環(huán)的索引，一定是表示 滑動窗口的終止位置。

那么問題來了， 滑動窗口的起始位置如何移動呢？

這里還是以題目中的示例來舉例，s=7， 數(shù)組是 2，3，1，2，4，3，來看一下查找的過程：

最后找到 4，3 是最短距離。

其實從動畫中可以發(fā)現(xiàn)滑動窗口也可以理解為雙指針法的一種！只不過這種解法更像是一個窗口的移動，所以叫做滑動窗口更適合一些。

在本題中實現(xiàn)滑動窗口，主要確定如下三點：

窗口內(nèi)是什么？
如何移動窗口的起始位置？
如何移動窗口的結(jié)束位置？
窗口就是 滿足其和 ≥ s 的長度最小的 連續(xù) 子數(shù)組。

窗口的起始位置如何移動：如果當(dāng)前窗口的值大于s了，窗口就要向前移動了（也就是該縮小了）。文章來源地址http://www.zghlxwxcb.cn/news/detail-655371.html

代碼實現(xiàn)

//@i want to舞動乾坤 2023/08/13
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int i=0;
        int result =INT32_MAX; //結(jié)果,要取得盡量大一點
        int sum=0;//定義累加和
        int sublength=0;
        for(int j=0;j<nums.size();j++){
            sum+=nums[j];
           while(sum>=target)//如果滿足
            {
               sublength=j-i+1;//計算子數(shù)組的長度
               result=result>sublength?sublength:result;//這里就是為什么result取得大的原因了,這步驟也可以改成： result=min(result,j-i+1);從而減少內(nèi)存
               sum-=nums[i++];//滑動窗口的精髓，動態(tài)更新sum的大小

            }
        }

        return result==INT32_MAX? 0 : result;//如果result沒有變化，代表沒有進入while循環(huán)，一直沒有找到大于等于sum的數(shù)。
    }
};

到了這里，關(guān)于【代碼隨想錄-Leetcode第六題：209. 長度最小的子數(shù)組】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！