# 0209. 長度最小的子數組 ## 題目地址(209. 長度最小的子數組) <https://leetcode-cn.com/problems/minimum-size-subarray-sum/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個含有 n 個正整數的數組和一個正整數 s ，找出該數組中滿足其和 ≥ s 的長度最小的 連續 子數組，并返回其長度。如果不存在符合條件的子數組，返回 0。 示例： 輸入：s = 7, nums = [2,3,1,2,4,3] 輸出：2 解釋：子數組 [4,3] 是該條件下的長度最小的子數組。 進階： 如果你已經完成了 O(n) 時間復雜度的解法, 請嘗試 O(n log n) 時間復雜度的解法。 ``` ``` ## 前置知識 - 滑動窗口 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 用滑動窗口來記錄序列， 每當滑動窗口中的 sum 超過 s， 就去更新最小值，并根據先進先出的原則更新滑動窗口，直至 sum 剛好小于 s  > 這道題目和 leetcode 3 號題目有點像，都可以用滑動窗口的思路來解決 ## 關鍵點 - 滑動窗口簡化操作(滑窗口適合用于求解這種要求`連續`的題目) ## 代碼 - 語言支持：JS，C++，Python Python Code： ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">minSubArrayLen</span><span class="hljs-params">(self, s: int, nums: List[int])</span> -> int:</span> l = total = <span class="hljs-params">0</span> ans = len(nums) + <span class="hljs-params">1</span> <span class="hljs-keyword">for</span> r <span class="hljs-keyword">in</span> range(len(nums)): total += nums[r] <span class="hljs-keyword">while</span> total >= s: ans = min(ans, r - l + <span class="hljs-params">1</span>) total -= nums[l] l += <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> <span class="hljs-params">0</span> <span class="hljs-keyword">if</span> ans == len(nums) + <span class="hljs-params">1</span> <span class="hljs-keyword">else</span> ans ``` ``` JavaScript Code： ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=209 lang=javascript * * [209] Minimum Size Subarray Sum * */</span> <span class="hljs-title">/** * @param {number} s * @param {number[]} nums * @return {number} */</span> <span class="hljs-keyword">var</span> minSubArrayLen = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">s, nums</span>) </span>{ <span class="hljs-keyword">if</span> (nums.length === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">const</span> slideWindow = []; <span class="hljs-keyword">let</span> acc = <span class="hljs-params">0</span>; <span class="hljs-keyword">let</span> min = <span class="hljs-params">null</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < nums.length + <span class="hljs-params">1</span>; i++) { <span class="hljs-keyword">const</span> num = nums[i]; <span class="hljs-keyword">while</span> (acc >= s) { <span class="hljs-keyword">if</span> (min === <span class="hljs-params">null</span> || slideWindow.length < min) { min = slideWindow.length; } acc = acc - slideWindow.shift(); } slideWindow.push(num); acc = slideWindow.reduce((a, b) => a + b, <span class="hljs-params">0</span>); } <span class="hljs-keyword">return</span> min || <span class="hljs-params">0</span>; }; ``` ``` C++ Code： ``` <pre class="calibre18">``` <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">minSubArrayLen</span><span class="hljs-params">(<span class="hljs-keyword">int</span> s, <span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>& nums)</span> </span>{ <span class="hljs-keyword">int</span> num_len= nums.size(); <span class="hljs-keyword">int</span> left=<span class="hljs-params">0</span>, right=<span class="hljs-params">0</span>, total=<span class="hljs-params">0</span>, min_len= num_len+<span class="hljs-params">1</span>; <span class="hljs-keyword">while</span> (right < num_len) { <span class="hljs-keyword">do</span> { total += nums[right++]; } <span class="hljs-keyword">while</span> (right < num_len && total < s); <span class="hljs-keyword">while</span> (left < right && total - nums[left] >= s) total -= nums[left++]; <span class="hljs-keyword">if</span> (total >=s && min_len > right - left) min_len = right- left; } <span class="hljs-keyword">return</span> min_len <= num_len ? min_len: <span class="hljs-params">0</span>; } }; ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N)，其中 N 為數組大小。 - 空間復雜度：O(1)O(1)O(1) 歡迎關注我的公眾號《腦洞前端》獲取更多更新鮮的LeetCode題解  ## 擴展 如果題目要求是 sum = s, 而不是 sum >= s 呢？ eg: ``` <pre class="calibre18">``` <span class="hljs-keyword">var</span> minSubArrayLen = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">s, nums</span>) </span>{ <span class="hljs-keyword">if</span> (nums.length === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">const</span> slideWindow = []; <span class="hljs-keyword">let</span> acc = <span class="hljs-params">0</span>; <span class="hljs-keyword">let</span> min = <span class="hljs-params">null</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < nums.length + <span class="hljs-params">1</span>; i++) { <span class="hljs-keyword">const</span> num = nums[i]; <span class="hljs-keyword">while</span> (acc > s) { acc = acc - slideWindow.shift(); } <span class="hljs-keyword">if</span> (acc === s) { <span class="hljs-keyword">if</span> (min === <span class="hljs-params">null</span> || slideWindow.length < min) { min = slideWindow.length; } slideWindow.shift(); } slideWindow.push(num); acc = slideWindow.reduce((a, b) => a + b, <span class="hljs-params">0</span>); } <span class="hljs-keyword">return</span> min || <span class="hljs-params">0</span>; }; ``` ``` 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。