<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 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 ![](https://img.kancloud.cn/9b/73/9b738d61208b2c1b9ed9a160968f03fc_826x753.jpg) > 這道題目和 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題解 ![](https://img.kancloud.cn/77/1d/771d6f53e2a51febbcb6fa97f2899ac3_1586x578.jpg) ## 擴展 如果題目要求是 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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看